Doya and XOR#11855

Doya and XOR

3 seconds

256 megabytes

Medium

Doya gave Miku an array $a$ of size $n$ and an integer $x$ and told her that for every $y$ ( $1 \leq y \leq x$ 1 \le y \le x) she has to count the number of pairs $i, j$ such that:

$i \leq j$ i \le j.
$a_{i} \oplus a_{j}$ a_i \oplus a_j is a multiple of $2^{y}$ 2^y, where $\oplus$ denotes the bitwise XOR operator.

Can you help her solve this problem?

Input

Each test contains multiple test cases.

The first line contains a single integer $t$ ( $1 \leq t \leq 1000$ 1 \le t \le 1000) — the number of test cases.

The first line of each test case contains two integers $n$ , $x$ ( $1 \leq n \leq 5 \cdot 1 0^{4}$ 1 \le n \le 5 \cdot 10^4, $1 \leq x \leq 30$ 1 \le x \le 30).

The second line of each test case contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \dots, a_n ( $0 \leq a_{i} \leq 2^{30}$ 0 \le a_i \le 2^{30}).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 1 0^{4}$ 5 \cdot 10^4.

Output

For each test case, print one line consisting of $x$ integers separated by a space (For every $y$ ( $1 \leq y \leq x$ 1 \le y \le x) you need to output the number of pairs $i, j$ ).

Examples

Example


2
3 3
1 2 3
5 13
104 23 12 1 0

%
4 3 3
9 8 6 5 5 5 5 5 5 5 5 5 5

Example 1

Note

For the first test case $a = [1, 2, 3]$ a = [1, 2, 3] and $x = 3$ x = 3, let's consider all values among the array $a$ :

$a_{1} \oplus a_{1} = 0$ a_1 \oplus a_1 = 0
$a_{2} \oplus a_{2} = 0$ a_2 \oplus a_2 = 0
$a_{3} \oplus a_{3} = 0$ a_3 \oplus a_3 = 0
$a_{1} \oplus a_{2} = 3$ a_1 \oplus a_2 = 3
$a_{1} \oplus a_{3} = 2$ a_1 \oplus a_3 = 2
$a_{2} \oplus a_{3} = 1$ a_2 \oplus a_3 = 1

Consider values of $y$ :

For $y = 1$ y = 1 : There are $3$ values with $0$ and a single value with $2$ , thus there're $4$ pairs : $(1, 1), (2, 2), (3, 3), (1, 3)$ (1, 1), (2, 2), (3, 3), (1, 3)
For $y = 2$ y = 2 : There are $3$ values with $0$ so we only consider them.
For $y = 3$ y = 3 : There are $3$ values with $0$ so we only consider them.

For the second test case $a = [104, 23, 12, 1, 0]$ a = [104, 23, 12, 1, 0] and $x = 13$ x = 13, let's consider all values among the array $a$ :

$a_{1} \oplus a_{1} = 0$ a_1 \oplus a_1 = 0
$a_{2} \oplus a_{2} = 0$ a_2 \oplus a_2 = 0
$a_{3} \oplus a_{3} = 0$ a_3 \oplus a_3 = 0
$a_{4} \oplus a_{4} = 0$ a_4 \oplus a_4 = 0
$a_{5} \oplus a_{5} = 0$ a_5 \oplus a_5 = 0
$a_{1} \oplus a_{2} = 127$ a_1 \oplus a_2 = 127
$a_{1} \oplus a_{3} = 100$ a_1 \oplus a_3 = 100
$a_{1} \oplus a_{4} = 105$ a_1 \oplus a_4 = 105
$a_{1} \oplus a_{5} = 104$ a_1 \oplus a_5 = 104
$a_{2} \oplus a_{3} = 27$ a_2 \oplus a_3 = 27
$a_{2} \oplus a_{4} = 22$ a_2 \oplus a_4 = 22
$a_{2} \oplus a_{5} = 23$ a_2 \oplus a_5 = 23
$a_{3} \oplus a_{4} = 13$ a_3 \oplus a_4 = 13
$a_{3} \oplus a_{5} = 12$ a_3 \oplus a_5 = 12
$a_{4} \oplus a_{5} = 1$ a_4 \oplus a_5 = 1

Consider values of $y$ :

For $y = 1$ y = 1 : There are $5$ values with $0$ and $4$ even numbers, thus there're $9$ pairs.
For $y = 2$ y = 2 : There are $5$ values with $0$ and $3$ multiples of $4$ , thus there're $8$ pairs.
For $y = 3$ y = 3 : There are $5$ values with $0$ and $1$ multiple of $8$ , which is $104$ , so there're $6$ pairs.
For $y \geq 4$ y \ge 4 : We only consider $0$ 's so the answer is $5$ .

Scoring

Subtask $1$ ( $5$ points): $a_{1} = a_{2} = a_{3} = \dots = a_{n}$ a_1 = a_2 = a_3 = \dots = a_n
Subtask $2$ ( $15$ points): $\sum n \leq 1000$ \sum n \le 1000
Subtask $3$ ( $20$ points): $x = 1$ x = 1
Subtask $4$ ( $30$ points): $a_{i}$ a_i is a power of $2$
Subtask $5$ ( $50$ points): $a_{i} \leq 1 0^{6}$ a_i \le 10^6
Subtask $6$ ( $80$ points): No additional constraints.