Great Sequence

题意翻译

一个正整数数列对于正整数 $x$ 被称为棒的，当且仅当此数列可以被拆分为若干对，每对中一个数是另一个数的 $x$ 倍。 换一种说法，一个数列 $a$ 的长度 $n$ 是一个偶数，并且这个数列存在一种排列方式，使得满足 $1\leq i\leq\frac n2$ 的每个正整数 $i$，符合 $a_{2i-1}x=a_{2i}$，那么我们称数列 $a$ 对于正整数 $x$ 是棒的。 Sam 有一个数列 $a$ 和一个正整数 $x$。请你帮助他让这个数列 $a$ 对于 $x$ 变成棒的：将若干个正整数加入数列中。请问最少要加入几个正整数？ $1\leq n\leq 2\times 10^5$，$2\leq x\leq 10^6$，$1\leq a_i\leq 10^9$

题目描述

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 $ .

输入输出样例

输入样例 #1

4
4 4
1 16 4 4
6 2
1 2 2 2 4 7
5 3
5 2 3 5 15
9 10
10 10 10 20 1 100 200 2000 3

输出样例 #1

0
2
3
3

说明

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.