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


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 20000$) — 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$.


-----Output-----

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


-----Examples-----

Input
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
Output
0
2
3
3


-----Note-----

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.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Sorting

Greedy algorithms


Solutions:
from enum import Enum, auto
import copy
import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		(n, x) = map(int, input().split())
		a = list(map(int, input().split()))
		a_sorted = sorted(a)
		stack = {}
		for aa in reversed(a_sorted):
			if aa * x in stack:
				if stack[aa * x] == 1:
					stack.pop(aa * x)
				else:
					stack[aa * x] -= 1
			elif aa in stack:
				stack[aa] += 1
			else:
				stack[aa] = 1
		print(sum(stack.values()))
main()


import sys
import math
from fractions import Fraction
from decimal import *
input = sys.stdin.readline
t = int(input())
while t > 0:
	inp = input().strip()
	arr = [int(x) for x in inp.split(' ')]
	n = arr[0]
	x = arr[1]
	inp = input().strip()
	arr = [int(x) for x in inp.split(' ')]
	arr.sort()
	numsdict = {}
	for num in arr[::-1]:
		if num * x in numsdict and numsdict[num * x] > 0:
			numsdict[num * x] -= 1
		elif num in numsdict:
			numsdict[num] += 1
		else:
			numsdict[num] = 1
	ans = 0
	for k in numsdict.keys():
		ans += numsdict[k]
	print(ans)
	t -= 1


import sys
import math
from sys import stdin, stdout

def get_ints_in_variables():
	return map(int, sys.stdin.readline().strip().split())

def get_int():
	return int(input())

def get_ints_in_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_of_list(n):
	return [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]

def get_string():
	return sys.stdin.readline().strip()

def main():
	for t in range(get_int()):
		(n, x) = get_ints_in_variables()
		arr = get_ints_in_list()
		mp = {}
		for i in range(0, n):
			if arr[i] not in mp:
				mp[arr[i]] = 1
			else:
				mp[arr[i]] += 1
		arr.sort()
		for i in range(0, n):
			if mp[arr[i]] > 0:
				tp = arr[i] * x
				if tp in mp:
					if mp[tp] > 0:
						mp[tp] -= 1
						mp[arr[i]] -= 1
		ans = 0
		for (key, val) in mp.items():
			ans += val
		print(ans)
main()


from bisect import bisect_left
out = []
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a.sort()
	used = [False] * n
	ans = 0
	i = 0
	j = bisect_left(a, a[0] * x)
	while j < n:
		t = a[i] * x
		while j < n and a[j] < t:
			j += 1
		if j < n and a[j] == t:
			used[j] = True
			used[i] = True
			j += 1
		else:
			ans += 1
			used[i] = True
		while i < n and used[i]:
			i += 1
		if i == n:
			break
	ans += used.count(False)
	out.append(ans)
for i in out:
	print(i)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	great = 0
	dic = {}
	for k in a:
		if k in dic:
			dic[k] += 1
		else:
			dic[k] = 1
	for i in dic:
		while dic[i] > 0:
			if i * x in dic and dic[i * x] > 0:
				dic[i] -= 1
				dic[i * x] -= 1
			else:
				great += dic[i]
				dic[i] = 0
	print(great)


def solve():
	(n, x) = map(int, input().split())
	ll = list(map(int, input().split()))
	ll.sort()
	count = 0
	mp = {}
	for i in ll:
		if i not in mp:
			mp[i] = 1
		else:
			mp[i] += 1
	for i in ll:
		if mp[i] > 0:
			if i * x in mp and mp[i * x] > 0:
				mp[i * x] -= 1
				mp[i] -= 1
			else:
				count += 1
				mp[i] -= 1
	return count
t = int(input())
while t:
	res = solve()
	print(res)
	t -= 1


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	m = {}
	for i in l[::-1]:
		if i in m:
			m[i] += 1
		else:
			m[i] = 1
		if x * i in m:
			if m[x * i]:
				m[x * i] -= 1
				m[i] -= 1
	print(sum(m.values()))


def main():
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	freq = {}
	for z in arr:
		if z not in freq:
			freq[z] = 0
		freq[z] += 1
	for (k, v) in freq.items():
		if x * k in freq:
			curr = min(v, freq[x * k])
			freq[k] -= curr
			freq[x * k] -= curr
	ans = 0
	for (k, v) in freq.items():
		ans += v
	return ans
for _ in range(int(input())):
	print(main())


import collections
import sys
input = sys.stdin.readline

def solve(n, x, arr):
	arr.sort()
	counter = collections.defaultdict(int)
	for num in arr:
		counter[num] += 1
	ans = 0
	used = collections.defaultdict(int)
	for num in arr:
		if num in used and used[num] > 0:
			used[num] -= 1
			continue
		if x * num in counter and counter[x * num] > 0:
			counter[x * num] -= 1
			used[x * num] += 1
		else:
			ans += 1
	print(ans)
	return
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	solve(n, x, arr)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	ht = {}
	for p in arr:
		if p in ht:
			ht[p] += 1
		else:
			ht[p] = 1
	pairs = 0
	arr.sort()
	for num in arr:
		if ht[num] > 0:
			if num * x in ht and ht[num * x] > 0:
				ht[num * x] -= 1
				ht[num] -= 1
				pairs += 1
	paired = pairs * 2
	print(n - paired)


def check(n, x, a):
	a.sort()
	data = {}
	for i in a[::-1]:
		if i not in data:
			data[i] = 1
		else:
			data[i] += 1
		val = i * x
		if val in data:
			if data[val]:
				data[i] -= 1
				data[val] -= 1
	return sum(data.values())
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	print(check(n, x, a))


t = int(input())
while t > 0:
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = sorted(arr)
	cnt = 0
	j = n - 1
	vis = [False] * n
	for i in range(n - 1, -1, -1):
		if vis[i] == True:
			continue
		if arr[i] % x == 0:
			f = arr[i] / x
			while j >= 0 and (vis[j] == True or arr[j] > f):
				j -= 1
			while j >= 0 and arr[j] == f and (vis[j] == False):
				vis[i] = True
				vis[j] = True
				cnt += 1
	print(n - 2 * cnt)
	t = t - 1


import sys
from collections import defaultdict

class Solution:

	def great_sequence(self, N, X, L):
		c = 0
		freq = defaultdict(int)
		for item in L:
			freq[item] += 1
		keys = list(freq.keys())
		keys.sort()
		for key in keys:
			while freq[key] > 0 and freq[key * X] > 0:
				freq[key] -= 1
				freq[key * X] -= 1
				c += 2
		return len(L) - c
T = int(sys.stdin.readline().strip())
for t_ in range(T):
	(N, X) = [int(x_) for x_ in sys.stdin.readline().strip().split(' ')]
	L = [int(x_) for x_ in sys.stdin.readline().strip().split(' ')]
	s = Solution()
	print(s.great_sequence(N, X, L))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = [int(i) for i in input().split()]
	d = {}
	o = set()
	res = 0
	for k in a:
		if k in d:
			d[k] += 1
		else:
			d[k] = 1
	l = sorted(list(d.keys()))
	for k in l:
		if d[k] == 0:
			continue
		if k * x in d:
			f = d[k]
			s = d[k * x]
			diff = f - s
			if diff >= 0:
				res += diff
				d[k * x] = 0
			else:
				d[k * x] -= f
		else:
			res += d[k]
	print(res)


def solve():
	(n, x) = [int(x) for x in input().split()]
	a = sorted([int(x) for x in input().split()])
	value_counts = {}
	for i in a:
		if i not in value_counts:
			value_counts[i] = 0
		value_counts[i] += 1
	good_pair = 0
	for i in a:
		if value_counts[i] <= 0:
			continue
		if i * x in value_counts and value_counts[i * x] > 0:
			value_counts[i] -= 1
			value_counts[i * x] -= 1
			good_pair += 1
	ans = sum(value_counts.values())
	print(ans)
for tc in range(int(input())):
	solve()


def solve():
	(n, x) = map(int, input().split())
	nums = list(map(int, input().split()))
	d = {a: 0 for a in nums}
	for c in nums:
		d[c] += 1
	res = 0
	for c in sorted(d):
		if d.get(c * x) != None:
			k1 = d[c]
			k2 = d[c * x]
			d[c] -= min(k1, k2)
			d[c * x] -= min(k1, k2)
	for c in d.keys():
		res += d[c]
	print(res)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	d = dict()
	for i in l:
		d[i] = d.get(i, 0) + 1
	d = {i: d[i] for i in sorted(d.keys())}
	c = 0
	for i in d:
		if i % x == 0 and i // x in d:
			t = min(d[i // x], d[i])
			c += 2 * t
			d[i] -= t
	print(n - c)


from collections import Counter
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = Counter(map(int, input().split()))
	ans = 0
	for i in sorted(a.keys()):
		if i * x in a and a[i] > 0:
			res = min(a[i], a[i * x])
			a[i] -= res
			a[i * x] -= res
	print(sum(a.values()))


from collections import Counter
for i in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	ls = Counter(l)
	for i in l:
		if i in ls and i * x in ls and (ls[i] > 0) and (ls[i * x] > 0):
			ls[i] -= 1
			ls[i * x] -= 1
	no = ls.values()
	print(sum(no))


for t in range(int(input())):
	(n, x) = map(int, input().split())
	a = [*map(int, input().split())]
	l = {}
	for i in a:
		if l.get(i, 0):
			l[i] += 1
		else:
			l[i] = 1
	for i in sorted(a):
		if l.get(i * x, 0):
			if l[i * x] != 0 and l[i] != 0:
				l[i * x] -= 1
				l[i] -= 1
	print(sum(l.values()))


t = int(input())
for tt in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	di = {}
	score = 0
	for i in range(n):
		if a[i] * x not in di:
			score += 1
			if a[i] not in di:
				di[a[i]] = 1
			else:
				di[a[i]] += 1
		elif di[a[i] * x] >= 1:
			score -= 1
			di[a[i] * x] -= 1
		else:
			score += 1
			if a[i] not in di:
				di[a[i]] = 1
			else:
				di[a[i]] += 1
	print(score)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = [int(v) for v in input().split()]
	a.sort()
	count = defaultdict(int)
	total = 0
	for ai in a:
		if ai % x != 0:
			count[ai] += 1
			continue
		if count[ai // x] != 0:
			total += 2
			count[ai // x] -= 1
		else:
			count[ai] += 1
	print(n - total)


n = int(input())
for i in range(n):
	(tam, x) = map(int, input().split())
	lista = list(map(int, input().split()))
	dicio = {}
	for item in lista:
		if item in dicio:
			dicio[item] += 1
		else:
			dicio[item] = 1
	total = 0
	for item in sorted(dicio):
		esperado = item * x
		if esperado not in dicio:
			total += dicio[item]
		elif dicio[item] <= dicio[esperado]:
			dicio[esperado] -= dicio[item]
			dicio[item] = 0
			continue
		elif dicio[item] > dicio[esperado]:
			total += dicio[item] - dicio[esperado]
			dicio[esperado] = 0
	print(total)


for _ in range(int(input())):
	(n, x) = list(map(int, input().split(' ')))
	nums = list(map(int, input().split(' ')))
	a = dict()
	for num in nums:
		if num in a:
			a[num] += 1
		else:
			a[num] = 1
	ans = 0
	nums.sort()
	for num in nums:
		if a[num] == 0:
			continue
		a[num] -= 1
		if num * x in a:
			if a[num * x] > 0:
				a[num * x] -= 1
			else:
				ans += 1
		else:
			ans += 1
	print(ans)


import math
from sys import stdin
from collections import Counter
input = stdin.readline
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = [int(i) for i in input().split()]
	s = set(a)
	d = Counter(a)
	a.sort()
	for i in range(n):
		if d[a[i]] > 0:
			if a[i] * x in s:
				if d[a[i] * x] > 0:
					d[a[i] * x] = d[a[i] * x] - 1
					d[a[i]] = d[a[i]] - 1
	c = 0
	for i in s:
		c = c + d[i]
	print(c)


def main():
	T = int(input())
	for x in range(T):
		(n, k) = list(map(int, input().split(' ')))
		array = list(map(int, input().split(' ')))
		array.sort()
		vis = {}
		for elem in array:
			if vis.get(elem) is None:
				vis[elem] = 1
			else:
				vis[elem] += 1
		for i in range(len(array)):
			temp = k * array[i]
			if vis.get(temp) is None:
				continue
			elif vis[temp] == 0 or vis[array[i]] == 0:
				continue
			vis[temp] -= 1
			vis[array[i]] -= 1
		count = 0
		for (key, val) in vis.items():
			if val > 0:
				count += val
		print(count)
main()


import math

def func(n, x, a):
	a.sort()
	m = {}
	for i in range(n):
		if m.get(a[i] / x) == None:
			if m.get(a[i]) == None:
				m[a[i]] = 1
			else:
				m[a[i]] += 1
		elif m.get(a[i] / x) > 0:
			m[a[i] / x] -= 1
			if m[a[i] / x] == 0:
				m.pop(a[i] / x)
	return sum(m.values())
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	print(func(n, k, a))


mod = 10 ** 9 + 7

def ri():
	return int(input())

def rl():
	return list(map(int, input().split()))

def rm():
	return map(int, input().split())
for _ in range(ri()):
	(n, x) = rm()
	a = rl()
	a.sort()
	d = {}
	c = 0
	for i in a:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for i in a:
		if d[i] > 0:
			d[i] -= 1
			if i * x not in d or d[i * x] == 0:
				c += 1
			else:
				d[i * x] -= 1
	print(c)


from collections import Counter
t = int(input())
while t > 0:
	(n, x) = map(int, input().split())
	a = Counter(map(int, input().split()))
	for i in sorted(a.keys()):
		if i * x in a and a[i] > 0:
			r = min(a[i], a[i * x])
			a[i] -= r
			a[i * x] -= r
	print(sum(a.values()))
	t -= 1


for iii in range(int(input())):
	(n, x) = map(int, input().split())
	q = list(map(int, input().split()))
	q.sort()
	q1 = {}
	for i in q:
		q1[i] = q1.get(i, 0) + 1
	cout = n
	for i in range(n):
		f = q[i] * x
		if q1[q[i]] == 0:
			continue
		if f in q1 and q1[f] > 0:
			q1[f] -= 1
			q1[q[i]] -= 1
			cout -= 2
	print(cout)


for t in range(int(input())):
	(n, x) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	m = {}
	for i in a:
		if i not in m:
			m[i] = 1
		else:
			m[i] += 1
	count = 0
	for i in a:
		if m[i] == 0:
			continue
		m[i] -= 1
		if i * x not in m or m[i * x] == 0:
			count += 1
		else:
			m[i * x] -= 1
	print(count)


from collections import Counter, defaultdict
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	neededNumber = defaultdict(int)
	for num in a:
		if neededNumber[num] != 0:
			neededNumber[num] -= 1
		else:
			neededNumber[x * num] += 1
	print(sum(neededNumber.values()))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	dp = {}
	for i in arr:
		if i in dp:
			dp[i] += 1
		else:
			dp[i] = 1
	arr.sort()
	ans = 0
	for i in arr:
		if i not in dp:
			continue
		if dp[i] == 0:
			continue
		dp[i] -= 1
		if i * k not in dp:
			ans += 1
		else:
			if dp[i * k] == 0:
				ans += 1
				continue
			dp[i * k] -= 1
	print(ans)


t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	(n, k) = (l[0], l[1])
	a = sorted(list(map(int, input().split())))
	d = {}
	for i in a:
		if i not in d.keys():
			d[i] = 1
		else:
			d[i] += 1
	c = 0
	for i in sorted(d.keys()):
		if d[i] > 0:
			if i * k in d.keys():
				if d[i * k] > 0:
					mi = min(d[i * k], d[i])
					d[i * k] -= mi
					d[i] -= mi
				else:
					c += d[i]
					d[i] = 0
				if d[i] > 0:
					c += d[i]
			else:
				c += d[i]
	print(c)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	arr = [int(ele) for ele in input().split()]
	arr.sort()
	dict = {}
	for ele in arr:
		dict[ele] = dict.get(ele, 0) + 1
	for ele in arr:
		if dict[ele] > 0:
			if ele * x in dict and dict[ele * x] > 0:
				dict[ele] -= 1
				dict[ele * x] -= 1
	count = 0
	for key in dict:
		count += dict[key]
	print(count)


import math
t = int(input())
while t > 0:
	t -= 1
	dct = {}
	(n, x) = map(int, input().split())
	nums = list(map(int, input().split()))
	nums.sort()
	for i in range(n):
		dct[nums[i]] = dct.get(nums[i], 0) + 1
	ans = 0
	for key in dct.keys():
		if key * x in dct:
			decrease = min(dct[key], dct[key * x])
			dct[key] -= decrease
			dct[key * x] -= decrease
		ans += dct[key]
	print(ans)


from collections import defaultdict
l = int(input())
for i in range(l):
	(n, x) = map(int, input().split())
	noli = list(sorted(map(int, input().split())))
	d = defaultdict(int)
	for j in noli:
		if d[j]:
			d[j] -= 1
		else:
			d[j * x] += 1
	t = sum(d.values())
	print(t)


a = int(input())
for i in range(a):
	(n, x) = map(int, input().split())
	A = [int(x) for x in input().split()]
	A.sort()
	numsdict = {}
	for num in A[::-1]:
		if num * x in numsdict and numsdict[num * x] > 0:
			numsdict[num * x] -= 1
		elif num in numsdict:
			numsdict[num] += 1
		else:
			numsdict[num] = 1
	ans = 0
	for k in numsdict.keys():
		ans += numsdict[k]
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	cnt = 0
	j = 0
	for i in range(n):
		while j < n - 1 and a[j] < a[i] * x:
			j += 1
		if a[j] == a[i] * x:
			cnt += 2
			a[j] = -1
			a[i] = -1
	print(n - cnt)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	nums = list(map(int, input().split()))
	o = sorted(nums)
	l = {x: 0 for x in o}
	for item in o:
		l[item] += 1
	for item in o:
		if l.get(item * x) and l.get(item * x) > 0 and l.get(item):
			l[item] -= 1
			l[item * x] -= 1
	print(sum(l.values()))


from collections import defaultdict

def solve(n, x, a):
	looking = defaultdict(int)
	for d in a:
		looking[d] += 1
	for d in sorted(a):
		if looking[d] > 0 and looking[d * x] > 0:
			looking[d] -= 1
			looking[d * x] -= 1
	print(sum(looking.values()))
debugmode = 0
if debugmode:
	with open('input.txt', 'r') as f:
		t = int(f.readline())
		for _ in range(t):
			(n, x) = list(map(int, f.readline().split()))
			a = list(map(int, f.readline().split()))
			solve(n, x, a)
else:
	t = int(input())
	for _ in range(t):
		(n, x) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		solve(n, x, a)


from collections import Counter
for t in range(int(input())):
	(n, x) = map(int, input().split())
	a = [*map(int, input().split())]
	l = Counter(a)
	for i in sorted(set(a)):
		if l.get(i * x, 0):
			e = min(l[i * x], l[i])
			l[i * x] -= e
			l[i] -= e
	print(sum(l.values()))


from collections import defaultdict
l = int(input())
for _ in range(0, l):
	(n, x) = map(int, input().split())
	numbers = [int(i) for i in input().split()]
	numbers.sort()
	d = defaultdict(int)
	for i in numbers:
		d[i] += 1
	ans = len(numbers)
	for key in d:
		if key % x == 0 and key // x in d and d[key // x]:
			ans -= 2 * min(d[key // x], d[key])
			minimal = min(d[key // x], d[key])
			d[key // x] -= minimal
			d[key] -= minimal
	print(ans)


import collections
t = int(input())
for i in range(t):
	(n, x) = input().split()
	n = int(n)
	x = int(x)
	ap = input().split()
	a = [int(y) for y in ap]
	a.sort()
	fr = collections.Counter(a)
	p = len(fr.keys())
	ctr = 0
	for j in fr.keys():
		if j * x in fr.keys():
			val = min(fr[j], fr[j * x])
			ctr += val
			fr[j] = fr[j] - val
			fr[j * x] = fr[j * x] - val
	print(n - 2 * ctr)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	d = {}
	for num in l:
		d[num] = d.get(num, 0) + 1
	for num in l:
		if d[num] > 0 and x * num in d and (d[x * num] > 0):
			d[num] -= 1
			d[x * num] -= 1
	res = 0
	for key in d:
		res += d[key]
	print(res)


def read_int():
	return int(input())

def read_int_map():
	return map(int, input().split())

def read_int_list():
	return list(map(int, input().split()))
t = read_int()
for _ in range(t):
	(n, x) = read_int_map()
	a = read_int_list()
	a.sort()
	res = 0
	p = 0
	for i in range(n):
		v = a[i]
		if v < 0:
			continue
		m = v * x
		while p < n:
			if a[p] >= m:
				break
			p += 1
		if p < n and a[p] == m:
			a[i] = -1
			a[p] = -1
		else:
			res += 1
	print(res)


from collections import Counter
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	ls = Counter(list(map(int, input().split())))
	keys = sorted(ls.keys())
	for item in keys:
		if ls[item * x] > 0:
			kom = min(ls[item], ls[item * x])
			ls[item] -= kom
			ls[item * x] -= kom
	print(sum(ls.values()))


from collections import Counter
from collections import defaultdict
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	inp = [int(i) for i in input().split()]
	c = Counter(inp)
	d = defaultdict(int, sorted(c.items(), key=lambda i: i[0]))
	for i in d:
		if i * x in d:
			t = min(d[i], d[i * x])
			d[i] -= t
			d[i * x] -= t
	print(sum(d.values()))


inp = lambda : list(map(int, input().split()))
t = int(input())
for _ in range(t):
	(n, x) = inp()
	a = inp()
	cnt = 0
	dct = dict()
	for el in a:
		if el in dct:
			dct[el] += 1
		else:
			dct[el] = 1
	a.sort()
	for el in a:
		if dct[el] == 0:
			continue
		if not el % x and el // x in dct and (dct[el // x] != 0):
			dct[el // x] -= 1
		elif x * el in dct and dct[x * el] != 0:
			dct[x * el] -= 1
		else:
			cnt += 1
		dct[el] -= 1
	print(cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = {}
	for i in range(n):
		if a[i] in b:
			b[a[i]] += 1
		else:
			b[a[i]] = 1
	c = 0
	for i in sorted(b.keys()):
		if i * k in b:
			if b[i * k] > b[i]:
				b[i * k] -= b[i]
				b[i] = 0
			else:
				b[i] -= b[i * k]
				b[i * k] = 0
				c += b[i]
		else:
			c += b[i]
			b[i] = 0
	print(c)


def solve(a, x):
	ans = 0
	t = dict()
	for i in a:
		if i not in t:
			t.__setitem__(i, 0)
		t[i] += 1
	sort_keys = sorted(list(t.keys()))
	for k in sort_keys:
		if k * x in t:
			minus = min(t[k], t[k * x])
			t[k] += -minus
			t[k * x] += -minus
		ans += t[k]
	return ans
test = int(input())
for i in range(0, test):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	print(solve(a, x))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	W = list(map(int, input().split()))
	Map1 = {}
	W.sort()
	for w in W:
		if w not in Map1:
			Map1[w] = 1
		else:
			Map1[w] += 1
	for key in Map1:
		if Map1[key] != 0:
			if key / x in Map1 and Map1[key / x] != 0:
				m91 = min(Map1[key], Map1[key / x])
				Map1[key / x] -= m91
				Map1[key] -= m91
	Total91 = 0
	for q in Map1:
		if Map1[q] != 0:
			Total91 += Map1[q]
	print(Total91)


t = int(input())
while t > 0:
	cnt = 0
	Dict = {}
	(n, x) = [int(item) for item in input().split()]
	list = [int(item) for item in input().split()]
	for i in list:
		if i in Dict:
			Dict[i] += 1
		else:
			Dict[i] = 1
	list.sort()
	for i in range(0, n):
		if list[i] * x in Dict:
			if Dict[list[i]] > 0 and Dict[list[i] * x] > 0:
				Dict[list[i]] -= 1
				Dict[list[i] * x] -= 1
			elif Dict[list[i]] > 0:
				cnt += 1
				Dict[list[i]] -= 1
		elif Dict[list[i]] > 0:
			cnt += 1
			Dict[list[i]] -= 1
	print(cnt)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	d = {}
	h = {}
	for i in range(n):
		if l[i] in d:
			d[l[i]] += 1
		else:
			d[l[i]] = 1
	l.sort()
	i = 0
	cnt = 0
	while i < n:
		if l[i] in h and h[l[i]] > 0:
			j = i
			while i < j + h[l[j]]:
				i += 1
			h[l[j]] = 0
		else:
			if l[i] * k in d and d[l[i] * k] > 0:
				d[l[i] * k] -= 1
				if l[i] * k not in h:
					h[l[i] * k] = 1
				else:
					h[l[i] * k] += 1
			else:
				cnt += 1
			i += 1
	print(cnt)


from collections import deque
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	dq = deque([])
	sol = 0
	for y in a:
		if len(dq) > 0:
			while dq[0] < y:
				dq.popleft()
				sol += 1
				if len(dq) == 0:
					break
		if len(dq) > 0 and y == dq[0]:
			dq.popleft()
			continue
		dq.append(y * x)
	print(sol + len(dq))


from collections import Counter
t = int(input())
for _ in range(t):
	(n, x) = (int(y) for y in input().split())
	nums = [int(y) for y in input().split()]
	nums.sort()
	remaining_nums = Counter(nums)
	paired = 0
	for z in nums:
		bigger = x * z
		if remaining_nums[z] == 0 or remaining_nums[bigger] == 0:
			continue
		paired += 2
		remaining_nums[z] -= 1
		remaining_nums[bigger] -= 1
	print(n - paired)


def solve():
	n = list(input().split())
	x = int(n[1])
	n = int(n[0])
	vec = list(input().split())
	for i in range(n):
		vec[i] = int(vec[i])
	memo = dict()
	for i in vec:
		if memo.get(i):
			memo[i] += 1
		else:
			memo[i] = 1
	ans = 0
	for el in sorted(memo.keys()):
		if memo.get(el):
			for i in range(memo[el]):
				if memo.get(el * x):
					memo[el * x] -= 1
					memo[el] -= 1
					if memo[el * x] == 0:
						memo.pop(el * x)
					if memo[el] == 0:
						memo.pop(el)
				else:
					ans += 1
	print(ans)
t = int(input())
while t > 0:
	t -= 1
	solve()


T = int(input())
for _ in range(T):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	d = {}
	for i in a:
		if i in d.keys():
			d[i] += 1
		else:
			d[i] = 1
	for i in a:
		if i not in d.keys():
			continue
		if i * x in d.keys():
			d[i] -= 1
			d[i * x] -= 1
			if d[i] == 0:
				d.pop(i)
			if d[i * x] == 0:
				d.pop(i * x)
		elif i % x == 0 and i // x in d.keys():
			d[i] -= 1
			d[i // x] -= 1
			if d[i] == 0:
				d.pop(i)
			if d[i // x] == 0:
				d.pop(i // x)
	count = 0
	for i in d.values():
		count += i
	print(count)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	i = 0
	cnt = 0
	dict = {}
	for i in arr:
		dict[i] = 0
	for i in arr:
		dict[i] += 1
	for i in dict:
		if i == 0:
			continue
		while dict[i] != 0:
			if x * i in dict:
				if dict[x * i] > 0:
					dict[i] -= 1
					dict[i * x] -= 1
				else:
					cnt += 1
					dict[i] -= 1
			else:
				cnt += 1
				dict[i] -= 1
	print(cnt)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007
t = inp()
for i in range(t):
	(n, x) = mul()
	l = seq()
	d = {}
	for i in l:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	ans = 0
	for i in sorted(d):
		v1 = d[i]
		v2 = d.get(i * x, 0)
		if v1 <= v2 and v2 != 0:
			d[i * x] -= v1
		elif v2 != 0:
			ans += v1 - v2
			d[i * x] = 0
		else:
			ans += v1
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = sorted(map(int, input().split()))
	q = {}
	o = 0
	for i in range(n):
		q[a[i]] = q.get(a[i], 0) + 1
	for i in range(n):
		if q[a[i]]:
			if a[i] * x in q and q[a[i] * x]:
				q[a[i]] -= 1
				q[a[i] * x] -= 1
	print(sum(q.values()))


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(sorted(map(int, input().split())))
	need = defaultdict(int)
	for y in a:
		if need[y]:
			need[y] -= 1
		else:
			need[x * y] += 1
	print(sum(need.values()))


from collections import Counter
t = int(input())
for z in range(t):
	(n, x) = map(int, input().split())
	l = [int(i) for i in input().split()]
	dic = Counter(l)
	l_d = sorted(dic.keys())
	ans = n
	for i in l_d:
		if dic[x * i]:
			if dic[x * i] >= dic[i]:
				dic[x * i] -= dic[i]
				ans -= 2 * dic[i]
				dic[i] = 0
			else:
				dic[i] -= dic[x * i]
				ans -= 2 * dic[x * i]
				dic[x * i] = 0
	print(ans)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	a = sorted(map(int, input().split()))
	ans = 0
	j = 0
	for i in range(n):
		while j < n - 1 and a[j] < a[i] * k:
			j += 1
		if a[j] == a[i] * k:
			ans += 2
			a[j] = -1
	print(n - ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	ans = 0
	h = {}
	for i in range(n):
		if l[i] not in h:
			h[l[i]] = 1
		else:
			h[l[i]] += 1
	for (i, j) in h.items():
		if i * x in h:
			if h[i * x] > j:
				h[i * x] -= j
				h[i] = 0
			elif h[i * x] < j:
				h[i] -= h[i * x]
				h[i * x] = 0
			else:
				h[i] = 0
				h[i * x] = 0
	for (i, j) in h.items():
		ans += j
	print(ans)


from collections import Counter

def fn(n, x, arr):
	arr.sort()
	cnt = Counter(arr)
	for num in arr:
		if num in cnt:
			if not cnt[num]:
				continue
		if num * x in cnt and cnt[num * x]:
			cnt[num * x] -= 1
			cnt[num] -= 1
	ans = 0
	for (k, v) in cnt.items():
		if v > 0:
			ans += v
	return ans
for _ in range(int(input())):
	(n, x) = input().split()
	arr = [int(i) for i in input().split()]
	print(fn(int(n), int(x), arr))


import heapq
from collections import *
import math

def solve():
	(n, x) = map(int, input().split())
	a = [int(i) for i in input().split()]
	d = defaultdict(int)
	ans = 0
	for i in a:
		d[i] += 1
	a.sort()
	for i in a:
		while d[i] > 0:
			if d[i * x] > 0:
				d[i * x] -= 1
			else:
				ans += 1
			d[i] -= 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


for t in range(int(input())):
	(n, x) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	hash_ = {i: 0 for i in set(a)}
	for i in a:
		hash_[i] += 1
	ans = 0
	for i in sorted(a):
		nxt = i * x
		if nxt in hash_:
			if hash_[nxt] > 0 and hash_[i] > 0:
				hash_[nxt] -= 1
				hash_[i] -= 1
			elif hash_[nxt] == 0 and hash_[i] > 0:
				hash_[i] -= 1
				ans += 1
		elif hash_[i] > 0:
			hash_[i] -= 1
			ans += 1
	print(ans)


import collections
t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = 0
	hmap = collections.defaultdict(int)
	for i in range(n):
		hmap[arr[i]] += 1
	for (i, j) in hmap.items():
		if i * x not in hmap:
			ans += j
			hmap[i] = 0
		elif hmap[i] > hmap[i * x]:
			ans += hmap[i] - hmap[i * x]
			hmap[i] = 0
			hmap[i * x] = 0
		elif hmap[i] < hmap[i * x]:
			hmap[i * x] -= hmap[i]
			hmap[i] = 0
		else:
			hmap[i] = 0
			hmap[i * x] = 0
	print(ans)


from math import ceil, log, floor, sqrt, gcd
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	d = {}
	for i in range(n):
		try:
			d[l[i]] += 1
		except:
			d[l[i]] = 1
	for i in d:
		if i * k in d:
			if d[i] > 0 and d[i * k] > 0:
				sub = min(d[i], d[i * k])
				d[i] -= sub
				d[i * k] -= sub
	print(sum(d.values()))


for t in range(int(input())):
	(n, x) = map(int, input().split())
	A = [int(i) for i in input().split()]
	d = dict()
	for i in A:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	A.sort()
	count = 0
	for i in range(n):
		(x1, x2) = (A[i], A[i] * x)
		if x1 in d and x2 in d:
			if d[x1] > 0 and d[x2] > 0:
				d[x1] -= 1
				d[x2] -= 1
			elif d[x1] > 0 and d[x2] == 0:
				count += 1
				d[x1] -= 1
		elif d[x1] > 0:
			count += 1
			d[x1] -= 1
	print(count)


import collections
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = collections.Counter(arr)
	ans = 0
	for k in sorted(d.keys()):
		if d[k * x] > 0:
			a = d[k * x]
			b = d[k]
			if b > a:
				ans += b - a
				d[k] = 0
				d[k * x] = 0
			else:
				d[k] = 0
				d[k * x] -= b
		else:
			ans += d[k]
	print(ans)


t = int(input())
for _ in range(t):
	(n, x) = [int(x) for x in input().split(' ')]
	l = sorted([int(x) for x in input().split(' ')])
	m = {}
	for a in l:
		if a not in m:
			m[a] = 1
		else:
			m[a] += 1
	ans = 0
	for a in l:
		if m[a] == 0:
			continue
		m[a] -= 1
		if a * x not in m or m[a * x] == 0:
			ans += 1
		else:
			m[a * x] -= 1
	print(ans)


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	a = sorted(map(int, input().split()))
	c = {}
	for x in a:
		c[x] = c.get(x, 0) + 1
	d = 0
	while 1:
		while a and (not c[a[-1]]):
			a.pop()
		if not a:
			break
		x = a.pop()
		c[x] -= 1
		if x % p or not c.get(x // p, 0):
			d += 1
		else:
			c[x // p] -= 1
	print(d)


import sys
import math
ttime = int(input())
for ccount in range(ttime):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	mark = [False for i in range(len(a))]
	pointer = 0
	cnt = 0
	for i in range(len(a)):
		if mark[i] == False:
			while pointer < len(a) and (a[pointer] < a[i] * x or mark[pointer]):
				pointer += 1
			if pointer < len(a) and a[pointer] == a[i] * x and (mark[pointer] == False):
				cnt += 1
				mark[pointer] = True
	print(len(a) - cnt * 2)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if a[i] in d:
			d[a[i]] += 1
		else:
			d[a[i]] = 1
	cnt = 0
	a.sort(reverse=True)
	for i in range(n):
		if a[i] in d:
			if a[i] % x == 0 and a[i] // x in d:
				d[a[i]] -= 1
				if d[a[i]] == 0:
					d.pop(a[i])
				d[a[i] // x] -= 1
				if d[a[i] // x] == 0:
					d.pop(a[i] // x)
			else:
				cnt += d[a[i]]
				d.pop(a[i])
	print(cnt)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	dic = {}
	s = set()
	for i in a:
		if i in dic:
			dic[i] += 1
		else:
			dic[i] = 1
			s.add(i)
	ans = 0
	s = list(s)
	s.sort()
	for i in s:
		for _ in range(dic[i]):
			if i * x in dic and dic[i * x] > 0:
				dic[i * x] -= 1
			else:
				ans += 1
				dic[i] = 0
	print(ans)


from collections import Counter, deque, defaultdict
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce
import sys
import decimal

def readIntLine():
	return [int(char) for char in input().split()]

def readCharLine():
	return [char for char in input().split()]

def solve():
	(n, x) = readIntLine()
	arr = readIntLine()
	counter = Counter(arr)
	nums = sorted([num for (num, count) in counter.items()])
	ans = 0
	for num in nums:
		count = counter[num]
		if count == 0:
			continue
		num2 = num * x
		if num2 not in counter or counter[num2] == 0:
			ans += count
		else:
			count2 = counter[num2]
			if count == count2:
				counter[num2] = 0
				continue
			elif count2 < count:
				counter[num2] = 0
				ans += count - count2
			else:
				counter[num2] -= count
	return ans
for _ in range(int(input())):
	print(solve())


t = int(input())
for i in range(0, t):
	(n, x) = [int(y) for y in input().split()]
	a = list(map(int, input().split()))
	a.sort()
	hash_map = {}
	for j in a:
		if hash_map.get(j) == None:
			hash_map[j] = 1
		else:
			hash_map[j] += 1
	keys = hash_map.keys()
	for k in keys:
		if hash_map.get(k * x) != None:
			if hash_map[k] > 0 and hash_map[x * k]:
				hash_map[x * k] -= hash_map[k]
				hash_map[k] = 0
	count = 0
	for k in keys:
		if hash_map[k] != 0:
			count += abs(hash_map[k])
	print(count)


import sys
from collections import Counter

class Solution:

	def call(self, input):
		problems = self.parse(input)
		for problem in problems:
			self.solve(problem)

	def parse(self, input):
		raw = [text.split(' ') for text in input]
		raw.pop(0)
		problems = []
		for i in range(len(raw) // 2):
			problems.append({'n': int(raw[2 * i][0]), 'x': int(raw[2 * i][1]), 'nums': [int(a) for a in raw[2 * i + 1]]})
		return problems

	def solve(self, problem):
		freq = dict(Counter(problem['nums']))
		cluster = []
		explored = set()
		nums = list(freq)
		nums.sort()
		for num in nums:
			if num in explored:
				continue
			explored.add(num)
			group = [freq[num]]
			while num * problem['x'] in freq.keys():
				num *= problem['x']
				explored.add(num)
				group.append(freq[num])
			cluster.append(group)
		remaining = 0
		for group in cluster:
			for i in range(len(group) - 1):
				pairs = min(group[i], group[i + 1])
				group[i] -= pairs
				group[i + 1] -= pairs
			remaining += sum(group)
		print(remaining)
		return remaining
input = sys.stdin.readlines()
Solution().call(input)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	l = sorted(l)
	c = 0
	d = {}
	for i in range(n):
		if l[i] in d:
			d[l[i]] += 1
		else:
			d[l[i]] = 1
	for i in l:
		if i in d and d[i] > 0:
			if x * i in d and d[x * i] > 0:
				d[i] -= 1
				d[x * i] -= 1
			else:
				c += 1
				d[i] -= 1
	print(c)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	(n, x) = map(int, input().split())
	A = list(map(int, input().split()))
	A.sort()
	net = collections.Counter(A)
	ans = 0
	for i in A:
		if net[i] > 0:
			comp = i * x
			if comp in net and net[comp] > 0:
				net[comp] -= 1
			else:
				ans += 1
			net[i] -= 1
	print(ans)
t = int(input())
while t != 0:
	solve()
	t -= 1