Read problems statements in Mandarin Chinese  and Russian. 
The Physics teacher in Tanu's class is teaching concepts of a bouncing ball. The rubber ball that she is using has the property that if the ball is dropped from height H then, it bounces back to maximum height H/F. So after first bounce it rises up to maximum height H/F, after second bounce to maximum height H/F^{2}, after third bounce to maximum height H/F^{3}, and so on.
The class has N children, and the teacher wants to select two children such that when the taller child drops the ball from his height, ball reaches a maximum height equal to the height of the shorter child after some (possibly zero) number of bounces. Note that zero bounces mean heights of the two children will be same. Given the heights of the children in the class Height[i], can you tell how many ways are there for the teacher to select two children for the demonstration? Note that when heights are same, the pair is only counted once (See first example for further clarification).

------ Input ------ 

First line contains T, number of testcases. Then 2*T lines follow, 2 per testcase.
First line of each testcase consists of two space-separated intergers N and F. Second line of each testcase contains N space-separated integers representing the array Height.

------ Output ------ 

For each testcase, print a single line containing the answer to the problem.

------ Constraints ------ 

$For 40 points: 1 ≤ T ≤ 100, 1 ≤ N ≤ 10^{3}, 2 ≤ F ≤ 10^{9}, 1 ≤ Height[i] ≤ 10^{9}
$$For 60 points: 1 ≤ T ≤ 100, 1 ≤ N ≤ 10^{4}, 2 ≤ F ≤ 10^{9}, 1 ≤ Height[i] ≤ 10^{9}$

----- Sample Input 1 ------ 
2
3 2
2 2 2
3 2
2 1 4
----- Sample Output 1 ------ 
3
3
----- explanation 1 ------ 
In the first case, the three pairs are (child 1, child 2), (child 2, child 3) and (child 1, child 3).
For the second case also, the three pairs are (child 1, child 2), (child 2, child 3) and (child 1, child 3).

Source: codechef | Difficulty: HARD
Tags: Sorting

Data structures


Solutions:
n = int(input())
for _ in range(n):
	(n, f) = [int(c) for c in input().split()]
	li = [int(c) for c in input().split()]
	count = 0
	a = []
	s = {}
	for i in li:
		h = i
		while h % f == 0:
			h /= f
		a.append(h)
		s[h] = 0
	for i in a:
		s[i] += 1
	for i in s:
		count += s[i] * (s[i] - 1) // 2
	print(count)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, f) = map(int, input().split())
	H = list(map(int, input().split()))
	dct = defaultdict(int)
	for i in range(n):
		base = H[i]
		while base % f == 0:
			base = base // f
		dct[base] += 1
	ans = 0
	for val in dct.values():
		ans += val * (val - 1) // 2
	print(ans)


for _ in range(int(input())):
	(N, F) = map(int, input().split())
	height = list(map(int, input().split()))
	height.sort()
	ans = 0
	dic = {}
	for i in range(N):
		while height[i] % F == 0:
			height[i] /= F
	for i in range(N):
		if height[i] not in dic:
			dic[height[i]] = 1
		else:
			dic[height[i]] += 1
	for i in list(dic.keys()):
		if dic[i] >= 2:
			ans += dic[i] * (dic[i] - 1) // 2
	print(ans)


from bisect import bisect_left, bisect_right
for _ in range(int(input())):
	(n, f) = [int(c) for c in input().split()]
	arr = [int(c) for c in input().split()]
	arr.sort()
	ans = 0
	mx = max(arr)
	for i in range(len(arr)):
		curr = arr[i]
		while curr <= mx:
			l = bisect_left(arr, curr, i + 1, n)
			r = bisect_right(arr, curr, i + 1, n)
			ans += r - l
			curr *= f
	print(ans)


from collections import Counter
for _ in range(int(input())):
	(n, f) = map(int, input().split())
	li = list(map(int, input().split()))
	for i in range(n):
		while li[i] % f == 0:
			li[i] = li[i] // f
	dic = Counter(li)
	c = 0
	for k in dic.keys():
		j = dic[k]
		c = c + j * (j - 1) // 2
	print(c)


from collections import Counter
t = int(input())
for test in range(1, t + 1):
	(n, f) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	narr = []
	for i in arr:
		tmp = i
		while tmp % f == 0:
			tmp /= f
		narr.append(tmp)
	dt = Counter(narr)
	c = 0
	for i in dt:
		c += (dt[i] - 1) * dt[i] / 2
	print(int(c))


def div(x, f):
	if x % f != 0:
		return x
	else:
		return div(x // f, f)
for i in range(int(input())):
	(n, f) = map(int, input().split())
	arr = list(map(int, input().split()))
	dictt = {}
	for x in arr:
		a = div(x, f)
		if a in dictt:
			dictt[a] += 1
		else:
			dictt[a] = 1
	count = 0
	for k in dictt.keys():
		if dictt[k] > 1:
			v = dictt[k]
			z = 0
			z = v * (v - 1) // 2
			count = count + z
	print(count)


import math
t = int(input())
while t > 0:
	t -= 1
	(n, f) = map(int, input().split())
	arr = list(map(int, input().strip().split()))[:n]
	dict = {}
	for i in range(n):
		l = int(math.log(arr[i], f))
		arr[i] /= pow(f, l)
	for i in range(n):
		if arr[i] in dict:
			dict[arr[i]] += 1
		else:
			dict[arr[i]] = 1
	count = 0
	for val in dict.values():
		count += val * (val - 1) / 2
	print(int(count))


for _ in range(int(input())):
	(n, f) = map(int, input().split())
	ar = map(int, input().split())
	(count, b, s) = (0, [], {})
	for i in ar:
		h = i
		while h % f == 0:
			h /= f
		b.append(h)
		s[h] = 0
	for i in b:
		s[i] += 1
	for i in s:
		count += s[i] * (s[i] - 1) // 2
	print(count)


from collections import defaultdict
for _ in range(int(input())):
	(n, h) = map(int, input().split())
	a = [int(i) for i in input().split()]
	count = 0
	mapi = defaultdict(int)
	for i in a:
		temp = i
		while temp % h == 0:
			temp = temp // h
		mapi[temp] += 1
	for i in mapi.values():
		count += (i - 1) * i // 2
	print(count)


for _ in range(int(input())):
	(n, f) = map(int, input().split())
	l = list(map(int, input().split()))
	c = l
	l = list(set(l))
	c.sort()
	k = 1
	dict = {}
	for i in range(1, n):
		if c[i] != c[i - 1]:
			dict[c[i - 1]] = k
			k = 1
		else:
			k = k + 1
		if i == n - 1:
			dict[c[i]] = k
	ans = 0
	for i in range(len(l)):
		if l[i] % f == 0:
			k = dict[l[i]]
			ans1 = 0
			y = int(l[i] / f)
			while y > 0:
				if dict.get(y) != None:
					ans1 = ans1 + dict[y]
				if y % f != 0:
					break
				else:
					y = int(y / f)
			ans = ans + ans1 * k + k * (k - 1) / 2
		else:
			ans = ans + dict[l[i]] * (dict[l[i]] - 1) / 2
	print(int(ans))


from collections import defaultdict
t = int(input())
for i in range(t):
	(n, f) = map(int, input().split())
	arr = [int(j) for j in input().split()]
	arr.sort()
	d = defaultdict(int)
	for x in arr:
		d[x] += 1
	ma = arr[-1]
	ans = 0
	for x in d:
		tempans = 0
		temp = x * f
		while temp <= ma:
			if temp in d:
				tempans += d[temp] * d[x]
			temp *= f
		tempans += d[x] * (d[x] - 1) // 2
		ans += tempans
	print(ans)


def count(arr, x, n, m):
	i = first(arr, m, n - 1, x)
	if i == -1:
		return 0
	j = last(arr, m, n - 1, x)
	return j - i + 1

def first(arr, i, j, val):
	x = -1
	while i <= j:
		mid = i + (j - i) // 2
		if arr[mid] > val:
			j = mid - 1
		elif arr[mid] == val:
			x = mid
			j = mid - 1
		else:
			i = mid + 1
	return x

def last(arr, i, j, val):
	x = -1
	while i <= j:
		mid = i + (j - i) // 2
		if arr[mid] > val:
			j = mid - 1
		elif arr[mid] == val:
			x = mid
			i = mid + 1
		else:
			i = mid + 1
	return x
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	d = l[-1]
	c = 0
	for i in range(n - 1):
		x = l[i]
		while x <= d:
			e = count(l, x, n, i + 1)
			c += e
			x *= k
	print(c)


for _ in range(int(input())):
	(n, f) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	for i in range(n):
		while arr[i] % f == 0:
			arr[i] //= f
	arr.sort()
	ans = 0
	cnt = 1
	cur = arr[0]
	for i in range(1, n):
		if arr[i] != cur:
			cur = arr[i]
			cnt = 0
		ans += cnt
		cnt += 1
	print(ans)


import sys, bisect
from bisect import bisect_left
input = sys.stdin.readline
(b, c, MAX) = ([], [], int(10000.0))
t = int(input().strip())
while t:
	(n, f) = map(int, input().strip().split())
	(i, j) = (0, 0)
	a = sorted([int(x) for x in input().strip().split()])
	while i < n:
		k = i
		while i < n and a[i] == a[k]:
			i += 1
		b.append(a[k])
		c.append(i - k)
		j += 1
	k = 0
	for i in range(len(b)):
		(d, y) = (c[i] * (c[i] - 1) // 2, f)
		while b[i] // y and b[i] % y == 0:
			j = bisect_left(b, b[i] // y)
			d += c[i] * c[j] if b[j] == b[i] // y else 0
			y = y * f
		k += d
	print(k)
	a.clear()
	b.clear()
	c.clear()
	t -= 1


from bisect import bisect_left
from bisect import bisect_right
t = int(input())
while t > 0:
	(n, k) = input().strip().split(' ')
	(n, k) = (int(n), int(k))
	count = 0
	a = []
	mapp = {}
	str = input().split()
	for s in str:
		x = int(s)
		while x % k is 0:
			x //= k
		a.append(x)
		mapp[x] = 0
	for i in a:
		mapp[i] += 1
	for i in mapp:
		count += mapp[i] * (mapp[i] - 1) // 2
	print(count)
	t -= 1