A famous student of AESC MSU, as you know, comes from Kostomuksha. Kostomuksha has a popular game called Doka.

The essence of Doka is as follows:

You are given an array A and an integer X. You want to calculate how many subarrays of this array have a geometric mean of X. 

Formally, calculate the number of pairs of integers (L, R) such that 1 ≤ L ≤ R ≤ N and
\sqrt[R-L+1]{A_{L} \cdot A_{L + 1} \cdot \ldots \cdot A_{R}} = X

------ Input Format ------ 

- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of two lines of input.
- The first line of each test case contains two space-separated integers N, X — the size of the array A and the required geometric mean.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For each test case, on a new line print the number of subarrays that satisfy the condition.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ X, A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

------ subtasks ------ 

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
3
3 3
3 3 3
4 4
1 2 3 4
4 54
36 81 54 54
----- Sample Output 1 ------ 
6
1
6
----- explanation 1 ------ 
Test case $1$: Every subarray has a geometric mean of $3$, and there are $6$ subarrays in total so the answer is $6$.

Test case $2$: The only subarray with a geometric mean of $4$ is the singleton array $[4]$, obtained with $L = R = 4$.

Test case $3$: The $6$ pairs of $(L, R)$ which have a geometric mean of $54$ are:
- $(1, 2)$, giving the subarray $[36, 81]$
- $(1, 3)$, giving the subarray $[36, 81, 54]$
- $(1, 4)$, giving the subarray $[36, 81, 54, 54]$
- $(3, 3)$, giving the subarray $[54]$
- $(3, 4)$, giving the subarray $[54, 54]$
- $(4, 4)$, giving the subarray $[54]$

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Range queries
Skill types: Range queries

Starter code:

Solutions:
for _ in range(int(input())):
	list1 = list(map(int, input().split()))
	(N, x) = (list1[0], list1[1])
	A = list(map(int, input().split()))
	flag = True
	for i in range(1, N):
		if A[i] != A[i - 1]:
			flag = False
			break
	if flag:
		print(N * (N + 1) // 2)
		continue
	else:
		count = 0
		for i in range(N):
			product = A[i] / x
			if product == 1:
				count += 1
			for j in range(i + 1, N):
				product = product * A[j] / x
				if product == 1:
					count += 1
		print(count)


import numpy

def gcd(n, d):
	while d != 0:
		t = d
		d = n % d
		n = t
	return n

def reduce(n, d):
	greatest = gcd(n, d)
	n /= greatest
	d /= greatest
	return (int(n), int(d))
T = int(input())
for numTests in range(T):
	(N, X) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')))
	A = numpy.array(A, dtype=float)
	data = numpy.log(A / X)
	data = numpy.cumsum(data)
	data = data.round(decimals=10)
	t = numpy.unique(data)
	total = 0
	for i in range(len(t)):
		tmp = numpy.where(data == t[i])[0]
		if t[i] == 0:
			total += len(tmp) * (len(tmp) + 1) // 2
		else:
			total += len(tmp) * (len(tmp) - 1) // 2
	print(total)


mod = 998244353

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

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())

def final(A, N, X):
	new = []
	for i in range(N):
		new.append([A[i], X])
	pre = [[1, 1]]
	for i in new:
		temp = [pre[-1][0] * i[0], pre[-1][1] * i[1]]
		curr = gcd(temp[0], temp[1])
		temp[0] //= curr
		temp[1] //= curr
		pre.append(temp)
	ct = dict()
	for i in pre:
		i = tuple(i)
		if i not in ct:
			ct[i] = 0
		ct[i] += 1
	ans = 0
	for i in ct:
		temp = ct.get(i) - 1
		ans += temp * (temp + 1) // 2
	return ans
for t in range(int(input())):
	from collections import Counter

	def gcd(x, y):
		while y:
			(x, y) = (y, x % y)
		return x

	def memodict(f):

		class memodict(dict):

			def __missing__(self, key):
				ret = self[key] = f(key)
				return ret
		return memodict().__getitem__

	def pollard_rho(n):
		if n & 1 == 0:
			return 2
		if n % 3 == 0:
			return 3
		s = (n - 1 & 1 - n).bit_length() - 1
		d = n >> s
		for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
			p = pow(a, d, n)
			if p == 1 or p == n - 1 or a % n == 0:
				continue
			for _ in range(s):
				prev = p
				p = p * p % n
				if p == 1:
					return gcd(prev - 1, n)
				if p == n - 1:
					break
			else:
				for i in range(2, n):
					(x, y) = (i, (i * i + 1) % n)
					f = gcd(abs(x - y), n)
					while f == 1:
						(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
						y = (y * y + 1) % n
						f = gcd(abs(x - y), n)
					if f != n:
						return f
		return n

	@memodict
	def prime_factors(n):
		if n <= 1:
			return Counter()
		f = pollard_rho(n)
		return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

	def distinct_factors(n):
		factors = [1]
		for (p, exp) in prime_factors(n).items():
			factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
		return factors

	def all_factors(n):
		(small, large) = ([], [])
		for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
			if not n % i:
				small.append(i)
				large.append(n // i)
		if small[-1] == large[-1]:
			large.pop()
		large.reverse()
		small.extend(large)
		return small

	def dv(c, d):
		(a, b) = (int(c), int(d))
		while a % b == 0:
			a //= b
		return a == 1 and c >= d

	def solve(S, X):
		count = 0
		rem = []
		pre = 0
		for i in range(len(S)):
			if dv(S[i], X):
				rem.append(S[pre:i])
				pre = i + 1
				count += 1
		for i in rem:
			temp = 1
			for j in i:
				temp *= j
			if dv(temp, X):
				count += 1
		return count

	def check(e, f):
		for i in f:
			while e % i == 0:
				e = e // i
		return e == 1
	(N, X) = mi()
	A = li()
	f = dict(prime_factors(X))
	f = list(f.keys())
	new = []
	i = 0
	while i < N:
		if check(A[i], f):
			j = i + 1
			while j < N and check(A[j], f):
				j += 1
			new.append(A[i:j])
			i = int(j)
		else:
			i += 1
	ans = 0
	for i in new:
		tmp = final(i, len(i), X)
		ans += tmp
	print(ans)


from sys import stdin
input = stdin.readline
PRIME = 1000000007

def solve(N, X, A):
	count = 0
	visited = set()
	for i in range(N):
		if i not in visited:
			product = 1
			power = 1
			n = 1
			for j in range(i, N):
				product = product * A[j] % PRIME
				power = power * X % PRIME
				if product == power:
					count += n
					n += 1
					visited.add(j + 1)
	return count
T = int(input().strip())
for problem in range(1, T + 1):
	(N, X) = [int(x) for x in input().strip().split()]
	A = [int(x) for x in input().strip().split()]
	print(solve(N, X, A))


from collections import defaultdict
from math import sqrt

def compute(eps, n, k):
	mp = defaultdict(int)
	sm = [0 for i in range(k)]
	mp[tuple(sm)] = 1
	ans = 0
	for i in range(n):
		for j in range(k):
			sm[j] += eps[i][j]
		kk = tuple(sm)
		if kk in mp:
			ans += mp[kk]
		mp[kk] += 1
	return ans

def prime_factors(n):
	p_factors = []
	exps = []
	ct = 0
	if n % 2 == 0:
		p_factors.append(2)
		exps.append(0)
		while n % 2 == 0:
			exps[ct] += 1
			n //= 2
		ct += 1
	for i in range(3, int(sqrt(n)) + 1, 2):
		if n % i == 0:
			p_factors.append(i)
			exps.append(0)
			while n % i == 0:
				n //= i
				exps[ct] += 1
			ct += 1
	if n != 1:
		p_factors.append(n)
		exps.append(1)
		ct += 1
	return (p_factors, exps, ct)
for _ in range(int(input())):
	(N, x) = map(int, input().split())
	a = list(map(int, input().split()))
	if x == 1:
		if 1 not in a:
			print(0)
			continue
		prod = 0
		l = 0
		r = 0
		while r < N:
			if a[r] != 1:
				l = r
				r += 1
			else:
				l = r
				while r < N and a[r] == 1:
					r += 1
				prod += (r - l) * (r - l + 1) // 2
		print(prod)
		continue
	(pf, exp, k) = prime_factors(x)
	eps = [[0] * k for i in range(N)]
	for i in range(N):
		prod = 1
		for j in range(k):
			p = pf[j]
			e = 0
			val = a[i]
			while val % p == 0:
				val //= p
				e += 1
			eps[i][j] = e - exp[j]
			prod *= p ** e
		if a[i] // prod > 1:
			for j in range(k):
				eps[i][j] = -int(100000000.0)
	print(compute(eps, N, k))