A. Great Sequence
brute force; greedy; sortings
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.