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

一个正整数序列被称为关于正整数 $x$ 的“优秀序列”，如果我们可以将该序列划分为若干对，使得每一对中第一个数乘以 $x$ 等于第二个数。更形式化地说，一个长度为 $n$ 的序列 $a$ 被称为关于正整数 $x$ 的“优秀序列”，当且仅当 $n$ 为偶数，且存在一个长度为 $n$ 的排列 $p$，使得对每个 $i$（$1 \le i \le \frac{n}{2}$）都有 $a_{p_{2i-1}} \cdot x = a_{p_{2i}}$。

Sam 有一个序列 $a$ 和一个正整数 $x$。请帮助他使该序列变为关于 $x$ 的优秀序列：求出需向序列 $a$ 中添加的最少正整数个数，使得添加后的序列关于 $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$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

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

对于每个测试用例，输出一个整数——即需要添加到序列 $a$ 末尾的最少整数个数，使得 $a$ 成为关于数字 $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.

在第一个测试用例中，Sam 很幸运，该序列对于数字 $4$ 已经是“优秀”的，因为你可以将其划分为如下数对：$(1, 4)$、$(4, 16)$。因此我们无需添加任何数（即添加 $0$ 个数）。

在第二个测试用例中，你可以在序列中添加数字 $1$ 和 $14$，之后便能将全部 $8$ 个整数划分为如下数对：$(1, 2)$、$(1, 2)$、$(2, 4)$、$(7, 14)$。无法通过添加少于 $2$ 个整数来修复该序列。