如果我们可以将正整数 $$$x$$$ 分成对,使得每对中第一个数字乘以 $$$x$$$ 等于第二个数字,那么对于正整数 $$$x$$$ 来说,正整数序列被称为“great”。更正式地说,如果 $$$n$$$ 是偶数并且存在大小为 $$$n$$$ 的排列 $$$p$$$,那么对于正整数 $$$x$$$ 来说,大小为 $$$n$$$ 的序列 $$$a$$$ 非常适合,这样对于每个 $$$i$$$ ($$$1 \le i \le \frac{n}{2}$$$) $$$a_{p_{2i-1}} \cdot x = a_{p_{2i}}$$$。
Sam 有一个序列 $$$a$$$ 和一个正整数 $$$x$$$。帮助他使序列变得更好:找到应添加到序列 $$$a$$$ 中的最小可能正整数数,以使其适合数字 $$$x$$$。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 20\,000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$、$$$x$$$ ($$$1 \le n \le 2 \cdot 10^5$$$、$$$2 \le x \le 10^6$$$)。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 可以添加到 $$$a$$$ 末尾以使其成为数字 $$$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
注意
在第一个测试用例中,Sam 很幸运,对于数字 $$$4$$$ 来说,序列已经很好了,因为你可以将它分成这样的对:$$$(1, 4)$$$, $$$(4, 16)$$$。因此我们可以添加 $$$0$$$ 数字。
在第二个测试用例中,您可以将数字 $$$1$$$ 和 $$$14$$$ 添加到序列中,然后您可以将所有 $$$8$$$ 整数分为以下对:$$$(1, 2)$$$、$$$(1, 2)$$$、$$$(2, 4)$$$、$$$(7, 14)$$$。不可能添加少于 $$$2$$$ 的整数来修复序列。