Последовательность положительных целых чисел называется великой для заданного положительного целого числа \(x\), если ее элементы можно разбить на пары так, что одно из чисел в паре при умножении на \(x\) будет равно другому числу в паре. Более формально, последовательность \(a\) длины \(n\) великая для заданного числа \(x\), если \(n\) четно и существует такая перестановка \(p\) размера \(n\), что для любого \(i\) (\(1 \le i \le \frac{n}{2}\)) выполняется, что \(a_{p_{2i-1}} \cdot x = a_{p_{2i}}\).
У Стаса есть последовательность положительных целых чисел \(a\) и положительное целое число \(x\). Помогите ему сделать последовательность великой: найдите минимальное количество положительных целых чисел, которое можно приписать к последовательности \(a\), чтобы она стала великой для числа \(x\).
Выходные данные
Для каждого набора входных данных выведите минимальное количество положительных целых чисел, которое можно добавить к последовательности \(a\), чтобы она стала великой для числа \(x\).
Примечание
В первом наборе входных данных последовательность уже является великой для числа \(4\), потому что числа можно разбить на пары \((1, 4)\), \((4, 16)\). Поэтому можно добавить \(0\) чисел.
Во втором наборе входных данных можно добавить числа \(1\) и \(14\) к последовательности, тогда получившиеся \(8\) чисел можно разбить на пары \((1, 2)\), \((1, 2)\), \((2, 4)\), \((7, 14)\). Меньше чем \(2\) числа добавить невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
0
2
3
3
|