A14952. Great Sequence

A sequence of positive integers is called great for a positive integer $x$ , if we can split it into pairs in such a way that in each pair the first number multiplied by $x$ is equal to the second number. More formally, a sequence $a$ of size $n$ is great for a positive integer $x$ , if $n$ is even and there exists a permutation $p$ of size $n$ , such that for each $i$ ( $1 \le i \le \frac{n}{2}$ ) $a_{p_{2i-1}} \cdot x = a_{p_{2i}}$ .

Sam has a sequence $a$ and a positive integer $x$ . Help him to make the sequence great: find the minimum possible number of positive integers that should be added to the sequence $a$ to make it great for the number $x$ .

Each test contains multiple test cases. The first line contains a single integer $t$ ( $1 \le t \le 20\,000$ ) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $n$ , $x$ ( $1 \le n \le 2 \cdot 10^5$ , $2 \le x \le 10^6$ ).

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ .

For each test case print a single integer — the minimum number of integers that can be added to the end of $a$ to make it a great sequence for the number $x$ .

In the first test case, Sam got lucky and the sequence is already great for the number $4$ because you can divide it into such pairs: $(1, 4)$ , $(4, 16)$ . Thus we can add $0$ numbers.

In the second test case, you can add numbers $1$ and $14$ to the sequence, then you can divide all $8$ integers into such pairs: $(1, 2)$ , $(1, 2)$ , $(2, 4)$ , $(7, 14)$ . It is impossible to add less than $2$ integers to fix the sequence.