该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师正在教学生们二进制的概念。给定 $n$ 个非负整数，徐老师想知道每个整数在二进制下有多少个 $1$。例如 $5$ 的二进制是 $101$，有 $2$ 个 $1$；$0$ 的二进制是 $0$，有 $0$ 个 $1$。

有 $T$ 组数据需要计算。

Format

Input

第一行一个正整数 $T$（$1 \leq T \leq 10$），表示测试组数。

对于每组测试，第一行一个正整数 $n$（$1 \leq n \leq 100$）。

第二行 $n$ 个非负整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 10^4$）。

Output

对于每组数据，输出一行 $n$ 个整数，表示每个数二进制下 $1$ 的个数，用空格分隔。

Samples

2
3
5 0 7
4
1 2 3 4

2 0 3
1 1 2 1

Limitation

1s, 1024KiB for each test case.