You are given an integer N. 

You are asked to find total number of integer pairs (A,B) such that
1 ≤ A,B ≤ N
A^{2}+B^{2}+gcd^{2}(A,B)+lcm^{2}(A,B)=N. Note that gcd^{2}(A, B) and lcm^{2}(A, B) denote the square of [gcd] and the square of [lcm] of numbers A and B respectively.

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

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The only line of each test case contains an integer N.

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

For each test case, output in a single line, number of valid pairs (A,B).

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

$1 ≤ T ≤ 10^{5}$
$4 ≤ N ≤ 10^{10}$
- Sum of $N$ over all test cases does not exceed $10^{10}$.

----- Sample Input 1 ------ 
3
4
10
20

----- Sample Output 1 ------ 
1
2
2

----- explanation 1 ------ 
Test case 1: The only valid pair is $(1, 1)$. Here:
- $1≤ 1 ≤ 4$.
- $1^{2} + 1^{2} + gcd^{2}(1,1) + lcm^{2}(1,1) = 1+1+1+1=4$.

Test case 2: Only $2$ pairs are possible. These are: $(1, 2)$ and $(2, 1)$.
- For pair $(1, 2)$: $1≤ 1, 2≤ 10$ and $1^{2}+2^{2}+gcd^{2}(1,2)+lcm^{2}(1,2)=1+4+1+4=10$. 

Test case 3: Only $2$ pairs are possible. These are: $(1, 3)$ and $(3, 1)$.
- For pair $(1, 3)$: $1≤ 1, 3≤ 20$ and $1^{2}+3^{2}+gcd^{2}(1,3)+lcm^{2}(1,3)=1+9+1+9=20$.

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
import itertools
import math

def factorize(n):

	def try_divisor(n, k, pfs):
		if n % k == 0:
			pfs[k] = 1
			n //= k
			while n % k == 0:
				pfs[k] += 1
				n //= k
		return n
	pfs = {}
	n = try_divisor(n, 2, pfs)
	n = try_divisor(n, 3, pfs)
	for i in itertools.count(start=1):
		n = try_divisor(n, 6 * i - 1, pfs)
		n = try_divisor(n, 6 * i + 1, pfs)
		if (6 * i + 1) ** 2 > n:
			break
	if n > 1:
		pfs[n] = 1
	return pfs

def recurse(lpfs, i, aa, bb):
	if i == len(lpfs):
		a = math.isqrt(aa - 1)
		b = math.isqrt(bb - 1)
		if a > 0 and b > 0 and (a * a + 1 == aa) and (b * b + 1 == bb) and (math.gcd(a, b) == 1):
			return 1
		else:
			return 0
	(p, e) = lpfs[i]
	if p == 2:
		if e % 2 == 1:
			return recurse(lpfs, i + 1, 2 * aa, bb) + recurse(lpfs, i + 1, aa, 2 * bb)
		else:
			return recurse(lpfs, i + 1, aa, bb) + recurse(lpfs, i + 1, 2 * aa, 2 * bb)
	else:
		return sum((recurse(lpfs, i + 1, aa * p ** j, bb * p ** k) for j in range(e + 1) for k in range(e - j + 1) if (e - j - k) % 2 == 0))
for _ in range(int(input())):
	pfs = factorize(int(input()))
	ok = True
	lpfs = []
	while pfs:
		(p, e) = pfs.popitem()
		if p % 4 == 3:
			if e % 2 == 1:
				ok = False
				break
		else:
			lpfs.append((p, e))
	print(recurse(lpfs, 0, 1, 1) if ok else 0)


import math

def gcd(a, b):
	while b != 0:
		temp = b
		b = a % b
		a = temp
	return a

def solve():
	n = int(input())
	if n % 2 != 0:
		return 0
	x = math.floor(math.sqrt(n))
	ans = 0
	for i in range(1, x + 1):
		for j in range(i, x + 1, i):
			a_sq = i * i
			lcm_sq = j * j
			num = lcm_sq * (n - a_sq - lcm_sq)
			if num <= 0:
				continue
			denom = lcm_sq + a_sq
			if num % denom != 0:
				continue
			b_sq = num // denom
			b = math.floor(math.sqrt(b_sq))
			if b * b != b_sq:
				continue
			if a_sq + b_sq >= n:
				continue
			g = gcd(i, b)
			gcd_sq = g * g
			if a_sq + b_sq + lcm_sq + gcd_sq == n:
				ans += 1
	return ans
for _ in range(int(input())):
	print(solve())


import sys
import os
import math
import collections
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	N = int(input())
	ans = []
	i = 1
	while i * i < N:
		if N % (i * i) == 0:
			A = N / (i * i)
			j = 1
			while (1 + j * j) * (1 + j * j) <= A:
				if A % (1 + j * j) == 0:
					B = int(A / (1 + j * j))
					sqrt = math.sqrt(B - 1)
					if sqrt == int(sqrt):
						C = j * i
						D = int(sqrt * i)
						if math.gcd(j, int(sqrt)) == 1:
							ans.append((C, D))
							ans.append((D, C))
				j += 1
		i += 1
	print(len(set(ans)))


import math as m

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return abs(a)

def ncr(N, R):
	return m.factorial(N) // (m.factorial(R) * m.factorial(N - R))

def getL():
	return [int(i) for i in input().split(' ')]

def getInt():
	return int(input())

def sPair(b):
	if int(b ** 0.5) == b ** 0.5:
		return True
	return False

def solve():
	n = getInt()
	if n % 2 == 1:
		print(0)
		return
	skrPair = set()
	for a in range(0, int((n // 2) ** 0.5) + 1):
		b = n - a * a
		if sPair(b):
			skrPair.add((a, int(b ** 0.5)))
	cnt = 0
	for each in skrPair:
		ab = each[0]
		gl = each[1]
		for a in range(1, int((n / 2) ** 0.5) + 1):
			b = a - ab
			if b > 0 and b < int((n / 2) ** 0.5) + 1:
				gc = gcd(a, b)
				lc = a * b / gc
				if gc + lc == gl:
					if a != b:
						cnt += 1
					cnt += 1
	print(cnt)
for _ in range(getInt()):
	solve()


import math
t = int(input())

def count_pairs(num):
	count = 0
	a = []
	w = int(math.sqrt(num))
	for i in range(1, w + 1):
		bsquare = num - i * i
		b = int(math.sqrt(bsquare))
		if b * b == bsquare:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			count += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q:
					count += 2
	return count
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(count_pairs(n))
	else:
		print(0)


import math

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def check(a, b, n):
	return a ** 2 + b ** 2 + gcd(a, b) ** 2 + LCM(a, b) ** 2 == n

def count(n, product):
	c = 0
	for hcf in product:
		product = n // (hcf * hcf)
		for i in range(2, sqrt(product)):
			if product % i == 0:
				(d1, d2) = (i, product // i)
				(a, b) = (math.sqrt(d1 - 1), math.sqrt(d2 - 1))
				if a == int(a) and b == int(b):
					if check(int(a) * hcf, int(b) * hcf, n):
						if a == b:
							c += 1
						else:
							c += 2
	return c

def solve():
	n = int(input())
	product = []
	i = 1
	while i * i <= n:
		if n % (i * i) == 0:
			product.append(i)
		i += 1
	print(count(n, product))
t = int(input())
for tt in range(t):
	solve()


import math

def counte(n):
	a = []
	count = 0
	w = int(math.sqrt(n))
	for i in range(1, w + 1):
		bs = n - i * i
		b = int(math.sqrt(bs))
		if b * b == bs:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			count += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q:
					count += 2
	return count
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(counte(n))
	else:
		print(0)


import math
t = int(input())

def ans(num):
	cnt = 0
	a = []
	br = []
	cr = []
	m = int(math.sqrt(num))
	for i in range(1, m + 1):
		bs = num - i * i
		b = int(math.sqrt(bs))
		if b * b == bs:
			a.append([i, b])
	for i in a:
		if i not in br:
			cr.append(i)
			br.append([i[1], i[0]])
	for i in cr:
		p1 = min(i[0], i[1])
		q1 = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			cnt += 1
		else:
			for j in range(1, q1):
				a = j
				b = a + p1
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q1:
					cnt += 2
	return cnt
for i in range(t):
	n = int(input())
	if n & 1 == 0:
		x = ans(n)
		print(x)
	else:
		print(0)


import math

def cpair(nt):
	cnt_no = 0
	a = []
	w = int(math.sqrt(nt))
	for i in range(1, w + 1):
		bsur = nt - i * i
		b = int(math.sqrt(bsur))
		if b * b == bsur:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			cnt_no += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q:
					cnt_no += 2
	return cnt_no
t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(cpair(n))
	else:
		print(0)


import math

def gcdandlcm(n):
	ans = 0
	a = []
	sq = int(math.sqrt(n))
	for i in range(1, sq + 1):
		square = n - i * i
		f = int(math.sqrt(square))
		if f * f == square:
			a.append([i, f])
	f = []
	c = []
	for j in a:
		if j not in f:
			c.append(j)
			f.append([j[1], j[0]])
	for k in c:
		p = min(k[0], k[1])
		q = max(k[0], k[1])
		if k[0] == 0 or k[1] == 0:
			ans += 1
		else:
			for j in range(1, q):
				a = j
				f = a + p
				g = math.gcd(a, f)
				l = a * f // g
				if g + l == q:
					ans += 2
	return ans
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(gcdandlcm(n))
	else:
		print(0)


import math

def count_pairs(n):
	count = 0
	a = []
	root = int(math.sqrt(n))
	for i in range(1, root + 1):
		bsqr = n - i * i
		b = int(math.sqrt(bsqr))
		if b * b == bsqr:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		mn = min(i[0], i[1])
		mx = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			count += 1
		else:
			for j in range(1, mx):
				a = j
				b = a + mn
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == mx:
					count += 2
	return count
t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 0:
		print(count_pairs(n))
	else:
		print(0)


from math import ceil, gcd, sqrt, floor
for _ in range(int(input())):
	n = int(input())
	count = 0
	i = 1
	while i * i <= n + 1:
		if n % (i * i) == 0:
			ab = n // (i * i)
			for j in range(1, int(ab ** 0.5) + 1):
				if ab % (j * j + 1) == 0:
					d = ab // (j * j + 1)
					d -= 1
					if ceil(sqrt(d)) == floor(sqrt(d)):
						if d != 0 and gcd(j, d) == 1:
							count += 1
		i += 1
	print(count)


from sys import stdin
from math import sqrt, ceil, floor, gcd
input = stdin.readline

def checkperfectsquare(x):
	if ceil(sqrt(x)) == floor(sqrt(x)):
		return True
	else:
		return False
for _ in range(int(input())):
	n = int(input())
	ans = 0
	for i in range(1, int(sqrt(n)) + 1):
		if n % (i * i) == 0:
			p = n // (i * i)
			for j in range(1, int(sqrt(p)) + 1):
				if p % (j * j + 1) == 0:
					c = j * j + 1
					d = p // c
					d -= 1
					if checkperfectsquare(d):
						if d != 0 and gcd(j, d) == 1:
							ans += 1
	print(ans)


import math
t = int(input())

def fun(n):
	flag = 0
	arrr = []
	win = int(math.sqrt(n))
	for i in range(1, win + 1):
		sq = n - i * i
		bc = int(math.sqrt(sq))
		if bc * bc == sq:
			arrr.append([i, bc])
	br = []
	cr = []
	for i in arrr:
		if i not in br:
			cr.append(i)
			br.append([i[1], i[0]])
	for i in cr:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			flag += 1
		else:
			for j in range(1, q):
				e = j
				r = e + p
				g = math.gcd(e, r)
				l = e * r // g
				if g + l == q:
					flag += 2
	return flag
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(fun(n))
	else:
		print(0)


import math
pareekshan_ka_maamala = int(input())

def joda_ginna(ank):
	mfk = 0
	cmp = 0
	ginna = 0
	a = []
	x = int(math.sqrt(ank))
	for loop in range(1, x + 1):
		chaukorb = ank - loop * loop
		q = int(math.sqrt(chaukorb))
		if q * q == chaukorb:
			a.append([loop, q])
	b = []
	cmp += 1
	y = []
	for loop in a:
		if loop not in b:
			y.append(loop)
			b.append([loop[1], loop[mfk]])
	for loop in y:
		p = min(loop[mfk], loop[1])
		s = max(loop[mfk], loop[1])
		if loop[mfk] == mfk or loop[mfk + 1] == mfk:
			ginna = ginna + 1
		else:
			for loop2 in range(1, s):
				a = loop2
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == s:
					ginna = ginna + 2
	return mfk + ginna
for loop in range(pareekshan_ka_maamala):
	inp = int(input())
	if inp % 2 != 0:
		print(0)
	else:
		print(joda_ginna(inp))


import math
test = int(input())

def ans(n):
	cnt = 0
	first_array = []
	second_array = []
	third_array = []
	pr = int(math.sqrt(n))
	for i in range(1, pr + 1):
		rem = n - i * i
		tr = int(math.sqrt(rem))
		if tr * tr == rem:
			first_array.append([i, tr])
	for i in first_array:
		if i in second_array:
			continue
		else:
			third_array.append(i)
			second_array.append([i[1], i[0]])
	for i in third_array:
		_min = min(i[0], i[1])
		_max = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			cnt += 1
		else:
			for j in range(1, _max):
				_1 = j
				_2 = _1 + _min
				gd = math.gcd(_1, _2)
				lm = _1 * _2 // gd
				if gd + lm == _max:
					cnt += 2
	return cnt
for i in range(test):
	n = int(input())
	if n % 2 == 1:
		print(0)
	else:
		print(ans(n))


import math
x = int(input())

def pairs(n):
	count = 0
	a = []
	s = int(math.sqrt(n))
	for i in range(1, s + 1):
		b2 = n - i * i
		b = int(math.sqrt(b2))
		if b * b == b2:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			count += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				gc = math.gcd(a, b)
				lc = a * b // gc
				if gc + lc == q:
					count += 2
	return count
for i in range(x):
	n = int(input())
	if n % 2 != 0:
		print(0)
	else:
		print(pairs(n))


import math

class Graph:

	def __init__(self, vertices):
		self.V = vertices
		self.graph = []

	def addEdge(self, u, v, w):
		self.graph.append([u, v, w])

	def printArr(self, dist):
		print('Vertex Distance from Source')
		for i in range(self.V):
			print('{0}\t\t{1}'.format(i, dist[i]))

	def BellmanFord(self, src):
		dist = [float('Inf')] * self.V
		dist[src] = 0
		for _ in range(self.V - 1):
			for (u, v, w) in self.graph:
				if dist[u] != float('Inf') and dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
		for (u, v, w) in self.graph:
			if dist[u] != float('Inf') and dist[u] + w < dist[v]:
				print('Graph contains negative weight cycle')
				return
		self.printArr(dist)

def ct_pairs(num):
	count = 0
	a = []
	wrea = int(math.sqrt(num))
	a1 = 38237
	a4 = 15626
	a3 = a1 - a4
	if a3 > a1:
		a4 += 2
	for i in range(1, wrea + 1):
		bsquare = num - i * i
		b = int(math.sqrt(bsquare))
		if b * b == bsquare:
			a.append([i, b])
	a11 = 38237
	a41 = 15626
	a31 = a11 - a41
	if a31 > a11:
		a41 += 2
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	a1 = 3837
	a4 = 1626
	a3 = a1 - a4
	if a3 > a1:
		a4 += 2
	for i in c:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			count += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q:
					count += 2
	a1 = 382
	a4 = 156
	a3 = a1 - a4
	if a3 > a1:
		a4 += 2
	return count
for i in range(int(input())):
	nat = int(input())
	a13 = 38237
	a44 = 15626
	a55 = 2637
	a13 = a13 - a44
	if a13 > 1:
		a44 += 2
	if nat % 2 == 0:
		print(ct_pairs(nat))
	else:
		print(0)


import math
t = int(input())

def cn_p(nu):
	co = 0
	a = []
	w = int(math.sqrt(nu))
	for i in range(1, w + 1):
		bsq = nu - i * i
		b = int(math.sqrt(bsq))
		if b * b == bsq:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		pi = min(i[0], i[1])
		qi = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			co += 1
		else:
			for j in range(1, qi):
				a = j
				b = a + pi
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == qi:
					co += 2
	return co
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(cn_p(n))
	else:
		print(0)


import math
test = int(input())

def pair(n):
	c = 0
	li = []
	num = int(math.sqrt(n))
	for i in range(1, num + 1):
		b = n - i * i
		g = int(math.sqrt(b))
		if g * g == b:
			li.append([i, g])
	res = []
	ans = []
	for i in li:
		if i not in res:
			ans.append(i)
			res.append([i[1], i[0]])
	for i in ans:
		x = max(i[0], i[1])
		y = min(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			c = c + 1
		else:
			for k in range(1, x):
				li = k
				g = li + y
				gc = math.gcd(li, g)
				lc = li * g // gc
				if gc + lc == x:
					c += 2
	return c
while test > 0:
	n = int(input())
	if n % 2 == 0:
		print(pair(n))
	else:
		print(0)
	test = test - 1


import math
T = int(input())

def pairs(n):
	c = 0
	l = []
	d = int(math.sqrt(n))
	for i in range(1, d + 1):
		bs = n - i * i
		b = int(math.sqrt(bs))
		if b * b == bs:
			l.append([i, b])
	m = []
	o = []
	for i in l:
		if i not in m:
			m.append([i[1], i[0]])
			o.append(i)
	for i in o:
		s = max(i[0], i[1])
		r = min(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			c += 1
		else:
			for j in range(1, s):
				y = j
				z = y + r
				g = math.gcd(y, z)
				l = y * z // g
				if g + l == s:
					c += 2
	return c
for i in range(T):
	N = int(input())
	if N % 2 == 0:
		print(pairs(N))
	else:
		print(0)


import math
t = int(input())

def cp(n):
	if n % 2 == 1:
		return 0
	else:
		c = 0
		a = []
		m = int(math.sqrt(n))
		for i in range(1, m + 1):
			x = n - i * i
			y = int(math.sqrt(x))
			if y * y == x:
				a.append([i, y])
		b = []
		d = []
		for j in a:
			if j not in b:
				d.append(j)
				b.append([j[1], j[0]])
		for j in d:
			u = min(j[0], j[1])
			v = max(j[0], j[1])
			if j[0] == 0 or j[1] == 0:
				c += 1
			else:
				for k in range(1, v):
					a = k
					b = a + u
					g = math.gcd(a, b)
					h = a * b // g
					if g + h == v:
						c += 2
	return c
for _ in range(t):
	n = int(input())
	print(cp(n))


import math
t = int(input())

def count_output(num):
	__count = 0
	a = []
	w = int(math.sqrt(num))
	for i in range(1, w + 1):
		b_square = num - i * i
		b = int(math.sqrt(b_square))
		if b * b == b_square:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			__count += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q:
					__count += 2
	return __count
for i in range(t):
	number = int(input())
	if number % 2 == 0:
		print(count_output(number))
	else:
		print(0)


import math
t = int(input())

def gulambi(N):
	fck = 0
	ar1 = []
	w = int(math.sqrt(N))
	for i in range(1, w + 1):
		sq = N - i * i
		b = int(math.sqrt(sq))
		if b * b == sq:
			ar1.append([i, b])
	br = []
	cr = []
	for i in ar1:
		if i not in br:
			cr.append(i)
			br.append([i[1], i[0]])
	for i in cr:
		chotu = min(i[0], i[1])
		baddu = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			fck = fck + 1
		else:
			for j in range(1, baddu):
				e = j
				r = e + chotu
				gre = math.gcd(e, r)
				l = e * r // gre
				if gre + l == baddu:
					fck = fck + 2
	return fck
for i in range(t):
	N = int(input())
	if N % 2 == 0:
		print(gulambi(N))
	else:
		print(0)


import math
test_case = int(input())

def Uttar(x):
	shabdkosh = 0
	lst = []
	y = int(math.sqrt(x))
	for a in range(1, y + 1):
		z_Square = x - a * a
		z = int(math.sqrt(z_Square))
		if z * z == z_Square:
			lst.append([a, z])
	z = []
	b = []
	for a in lst:
		if a not in z:
			b.append(a)
			z.append([a[1], a[0]])
	for a in b:
		x1 = min(a[0], a[1])
		x2 = max(a[0], a[1])
		if a[0] == 0 or a[1] == 0:
			shabdkosh += 1
		else:
			for a1 in range(1, x2):
				lst = a1
				z = lst + x1
				y1 = math.gcd(lst, z)
				y2 = lst * z // y1
				if y1 + y2 == x2:
					shabdkosh += 2
	return shabdkosh
for a in range(test_case):
	x = int(input())
	if x % 2 == 0:
		print(Uttar(x))
	else:
		print(0)


from collections import defaultdict
import math

def solve():
	t = int(input())
	while t:
		t -= 1
		num = int(input())
		if num % 2 == 1:
			print('0')
		else:
			count = 0
			a = []
			rnum = int(math.sqrt(num))
			for num1 in range(1, rnum + 1):
				o_sq = num - num1 * num1
				num2 = int(math.sqrt(o_sq))
				if num2 * num2 == o_sq:
					a.append([num1, num2])
			x = []
			y = []
			for i in a:
				if i not in x:
					y.append(i)
					x.append([i[1], i[0]])
			for i in y:
				L = min(i[0], i[1])
				M = max(i[0], i[1])
				if i[0] == 0 or i[1] == 0:
					count += 1
				else:
					for j in range(1, M):
						a = j
						b = a + L
						g = math.gcd(a, b)
						l = a * b // g
						if g + l == M:
							count += 2
			print(count)
solve()


import math
n = int(input())

def ans(l):
	c = 0
	u = []
	s = int(math.sqrt(l))
	for i in range(1, s + 1):
		secondsquare = l - i * i
		p = int(math.sqrt(secondsquare))
		if p * p == secondsquare:
			u.append([i, p])
	a = []
	b = []
	for i in u:
		if i not in a:
			b.append(i)
			a.append([i[1], i[0]])
	for i in b:
		j = min(i[0], i[1])
		k = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			c += 1
		else:
			for o in range(1, k):
				h = o
				z = h + j
				g = math.gcd(h, z)
				lc = h * z // g
				if g + lc == k:
					c += 2
	return c
for i in range(n):
	t = int(input())
	if t % 2 == 0:
		print(ans(t))
	else:
		print(0)


import math

def countPairs(n):
	cout = 0
	a = []
	w = int(math.sqrt(n))
	for i in range(1, w + 1):
		bSquare = n - i * i
		b = int(math.sqrt(bSquare))
		if b * b == bSquare:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			cout += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q:
					cout += 2
	return cout
t = int(input(''))
for i in range(t):
	n = int(input(''))
	if n % 2 == 0:
		print(countPairs(n))
	else:
		print(0)


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

def cp(number):
	count = 0
	arr = []
	w = int(math.sqrt(number))
	for i in range(1, w + 1):
		bs = number - i * i
		b = int(math.sqrt(bs))
		if b * b == bs:
			arr.append([i, b])
	brr = []
	crr = []
	for i in arr:
		if i not in brr:
			crr.append(i)
			brr.append([i[1], i[0]])
	for i in crr:
		x = min(i[0], i[1])
		y = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			count += 1
		else:
			for j in range(1, y):
				arr = j
				brr = arr + x
				gc = math.gcd(arr, brr)
				lc = arr * brr // gc
				if gc + lc == y:
					count += 2
	return count
t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(cp(n))
	else:
		print(0)


import math
t = int(input())

def fun(n):
	counter = 0
	arr = []
	wow = int(math.sqrt(n))
	for i in range(1, wow + 1):
		sqirt = n - i * i
		bob = int(math.sqrt(sqirt))
		if bob * bob == sqirt:
			arr.append([i, bob])
	bru = []
	cru = []
	for i in arr:
		if i not in bru:
			cru.append(i)
			bru.append([i[1], i[0]])
	for i in cru:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			counter += 1
		else:
			for j in range(1, q):
				eh = j
				reh = eh + p
				guh = math.gcd(eh, reh)
				l = eh * reh // guh
				if guh + l == q:
					counter += 2
	return counter
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(fun(n))
	else:
		print(0)


import math

def copair(num):
	c = 0
	a = []
	m = int(math.sqrt(num))
	for i in range(1, m + 1):
		bs = num - i * i
		b = int(math.sqrt(bs))
		if b * b == bs:
			a.append([i, b])
	ba = []
	ca = []
	for i in a:
		if i not in ba:
			ca.append(i)
			ba.append([i[1], i[0]])
	for i in ca:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[1] == 0 or i[0] == 0:
			c += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q:
					c += 2
	return c

def solve():
	n = int(input())
	if n % 2 == 0:
		print(copair(n))
	else:
		print(0)
for i in range(int(input())):
	solve()


import math
f = int(input())

def megha_pairs(num):
	megha = 0
	a = []
	p = int(math.sqrt(num))
	for i in range(1, p + 1):
		msquare = num - i * i
		m = int(math.sqrt(msquare))
		if m * m == msquare:
			a.append([i, m])
	m = []
	c = []
	for i in a:
		if i not in m:
			c.append(i)
			m.append([i[1], i[0]])
	for i in c:
		t = min(i[0], i[1])
		x = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			megha += 1
		else:
			for j in range(1, x):
				a = j
				m = a + t
				g = math.gcd(a, m)
				l = a * m // g
				if g + l == x:
					megha += 2
	return megha
for i in range(f):
	ayush = int(input())
	if ayush % 2 == 0:
		print(megha_pairs(ayush))
	else:
		print(0)


import math

def pairsCounter(N):
	counter = 0
	a = []
	v = int(N ** 0.5)
	for i in range(1, v + 1):
		sq_b = N - i * i
		b = int(sq_b ** 0.5)
		if b * b == sq_b:
			a.append([i, b])
	b = list()
	c = list()
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		m = min(i[0], i[1])
		n = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			counter = counter + 1
		else:
			for j in range(1, n):
				a = j
				b = a + m
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == n:
					counter = counter + 2
	return counter
testCases = int(input())
for k in range(testCases):
	N = int(input())
	if N % 2 == 0:
		print(pairsCounter(N))
	else:
		print(0)


import math

def pairs(n):
	cn = 0
	arr = []
	w = int(math.sqrt(n))
	for i in range(1, w + 1):
		bsq = n - i * i
		b = int(math.sqrt(bsq))
		if b * b == bsq:
			arr.append([i, b])
	b = []
	c = []
	for i in arr:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			cn += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q:
					cn += 2
	return cn
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(pairs(n))
	else:
		print(0)


import math
ab = int(input())

def test_p(nu):
	asd = 0
	ac = []
	ad = int(math.sqrt(nu))
	for i in range(1, ad + 1):
		squarenum = nu - i * i
		bd = int(math.sqrt(squarenum))
		if bd * bd == squarenum:
			ac.append([i, bd])
	bd = []
	cd = []
	for i in ac:
		if i not in bd:
			cd.append(i)
			bd.append([i[1], i[0]])
	for i in cd:
		pr = min(i[0], i[1])
		qr = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			asd += 1
		else:
			for j in range(1, qr):
				ac = j
				bd = ac + pr
				gc = math.gcd(ac, bd)
				li = ac * bd // gc
				if gc + li == qr:
					asd += 2
	return asd
for i in range(ab):
	k = int(input())
	if k % 2 == 0:
		print(test_p(k))
	else:
		print(0)


import math

def fun(n):
	count = 0
	x = []
	y = int(math.sqrt(n))
	for j in range(1, y + 1):
		bs = n - j * j
		b = int(math.sqrt(bs))
		if b * b == bs:
			x.append([j, b])
	p = []
	q = []
	for j in x:
		if j not in p:
			q.append(j)
			p.append([j[1], j[0]])
	for j in q:
		r = min(j[0], j[1])
		s = max(j[0], j[1])
		if j[0] == 0 or j[1] == 0:
			count += 1
		else:
			for k in range(1, s):
				l = k
				t = r + l
				g1 = math.gcd(l, t)
				l1 = l * t // g1
				if g1 + l1 == s:
					count += 2
	return count
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(fun(n))
	else:
		print(0)


import math

def pair(n):
	cnt = 0
	a = []
	s = int(math.sqrt(n))
	for i in range(1, s + 1):
		x2 = n - i * i
		x = int(math.sqrt(x2))
		if x * x == x2:
			a.append([i, x])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			cnt += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q:
					cnt += 2
	return cnt
for t in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print(pair(n))
	else:
		print(0)


import math
t = int(input())

def findSquares(n):
	ans = []
	nsqrt = int(math.sqrt(n))
	for i in range(1, nsqrt + 1):
		jsq = n - i * i
		j = int(math.sqrt(jsq))
		if j * j == jsq:
			ans.append([i, j])
	return ans

def solve(n):
	squares = findSquares(n)
	b = []
	c = []
	for i in squares:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	count = 0
	for i in c:
		a = min(i[0], i[1])
		b = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			count += 1
		else:
			for j in range(1, b):
				first = j
				second = j + a
				gcd = math.gcd(first, second)
				lcm = first * second // gcd
				if gcd + lcm == b:
					count += 2
	return count
for i in range(t):
	n = int(input())
	if n % 2 != 0:
		print(0)
	else:
		print(solve(n))


from math import sqrt
from math import gcd

def helper(num):
	count = 0
	A = []
	s = int(sqrt(num))
	for i in range(1, s + 1):
		Sq = num - i ** 2
		Sq1 = int(sqrt(Sq))
		if Sq1 ** 2 == Sq:
			A.append([i, Sq1])
	B = []
	C = []
	for a in A:
		if a not in B:
			C.append(a)
			B.append([a[1], a[0]])
	for c in C:
		a = min(c)
		b = max(c)
		if c[0] == 0 or c[1] == 0:
			count += 1
		else:
			for i in range(1, b):
				u = i
				v = u + a
				g = gcd(u, v)
				l = u * v // g
				if g + l == b:
					count += 2
	return count
test = int(input())
while test:
	n = int(input())
	if n % 2 == 0:
		print(helper(n))
	else:
		print(0)
	test -= 1


import math
ttgggg = int(input())

def kkra(n):
	k = 0
	a = []
	md = int(math.sqrt(n))
	for i in range(1, md + 1):
		bsquare = n - i * i
		b = int(math.sqrt(bsquare))
		if b * b == bsquare:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		x = min(i[0], i[1])
		y = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			k += 1
		else:
			for j in range(1, y):
				a = j
				b = a + x
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == y:
					k += 2
	return k
for i in range(ttgggg):
	n = int(input())
	if n % 2 == 0:
		print(kkra(n))
	else:
		print(0)


import math
tt = int(input())

def d_mahendra(n):
	ans = 0
	a = []
	m = int(math.sqrt(n))
	for i in range(1, m + 1):
		bsquare = n - i * i
		b = int(math.sqrt(bsquare))
		if b * b == bsquare:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		x = min(i[0], i[1])
		y = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			ans += 1
		else:
			for j in range(1, y):
				a = j
				b = a + x
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == y:
					ans += 2
	return ans
for i in range(tt):
	n = int(input())
	if n % 2 == 0:
		print(d_mahendra(n))
	else:
		print(0)


test = int(input())

def pair(num):
	import math
	a = []
	cou = 0
	w = int(math.sqrt(num))
	for i in range(1, w + 1):
		bsq = num - i * i
		b = int(math.sqrt(bsq))
		if b * b == bsq:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		mini = min(i[0], i[1])
		maxi = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			cou += 1
		else:
			for j in range(1, maxi):
				a1 = j
				b1 = a1 + mini
				g = math.gcd(a1, b1)
				l = a1 * b1 // g
				if g + l == maxi:
					cou += 2
	return cou
for i in range(test):
	num = int(input())
	if num % 2 == 0:
		print(pair(num))
	else:
		print(0)


import math
t = int(input())

def solve(n):
	count = 0
	a = []
	end = int(math.sqrt(n))
	for i in range(1, end + 1):
		bsq = n - i * i
		b = int(math.sqrt(bsq))
		if b * b == bsq:
			a.append([i, b])
	b = []
	c = []
	for i in a:
		if i not in b:
			c.append(i)
			b.append([i[1], i[0]])
	for i in c:
		p = min(i[0], i[1])
		q = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			count += 1
		else:
			for j in range(1, q):
				a = j
				b = a + p
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == q:
					count += 2
	return count
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(solve(n))
	else:
		print(0)


import math
t = int(input())

def counterPair(num):
	cnt = 0
	v1 = []
	z = int(math.sqrt(num))
	for i in range(1, z + 1):
		bsqt = num - i * i
		b = int(math.sqrt(bsqt))
		if b * b == bsqt:
			v1.append([i, b])
	v2 = []
	v3 = []
	for i in v1:
		if i not in v2:
			v3.append(i)
			v2.append([i[1], i[0]])
	for i in v3:
		s = min(i[0], i[1])
		t = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			cnt += 1
		else:
			for j in range(1, t):
				a = j
				b = a + s
				g = math.gcd(a, b)
				l = a * b // g
				if g + l == t:
					cnt += 2
	return cnt
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(counterPair(n))
	else:
		print(0)


import math

def solve(n):
	if n % 2 != 0:
		print(0)
		return
	cnt = 0
	l = []
	s = math.floor(math.sqrt(n))
	for i in range(1, s + 1):
		bs = n - i * i
		b = math.floor(math.sqrt(bs))
		if b * b == bs:
			l.append([i, b])
	a = []
	b = []
	for i in l:
		if i not in a:
			b.append(i)
			a.append([i[1], i[0]])
	for i in b:
		x = min(i[0], i[1])
		y = max(i[0], i[1])
		if i[0] == 0 or i[1] == 0:
			cnt += 1
		else:
			for j in range(1, y):
				p = j
				q = p + x
				g = math.gcd(p, q)
				l = p * q // g
				if g + l == y:
					cnt += 2
	print(cnt)

def main():
	for _ in range(int(input())):
		n = int(input())
		solve(n)
main()


from collections import Counter, deque
from collections import OrderedDict, defaultdict
import math
from random import randint
from bisect import bisect, bisect_left
import sys
import re

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def check(a, b, n):
	return a ** 2 + b ** 2 + gcd(a, b) ** 2 + LCM(a, b) ** 2 == n

def count(n, product):
	c = 0
	for hcf in product:
		product = n // (hcf * hcf)
		for i in range(2, sqrt(product)):
			if product % i == 0:
				(d1, d2) = (i, product // i)
				(a, b) = (math.sqrt(d1 - 1), math.sqrt(d2 - 1))
				if a == int(a) and b == int(b):
					if check(int(a) * hcf, int(b) * hcf, n):
						if a == b:
							c += 1
						else:
							c += 2
	return c

def solve():
	n = int(input())
	product = []
	i = 1
	while i * i <= n:
		if n % (i * i) == 0:
			product.append(i)
		i += 1
	print(count(n, product))
t = int(input())
for tt in range(t):
	solve()


from collections import Counter, deque
from collections import OrderedDict, defaultdict
import math
from random import randint
from bisect import bisect, bisect_left
import sys
import re
MOD = 10 ** 9 + 7
MAX = -sys.maxsize
MIN = sys.maxsize

class get:

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

	def str():
		return input().split()

	def float():
		return list(map(float, input().split()))

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

def sqrt(x):
	return int(math.sqrt(x)) + 1

def gcd(*args):
	result = args[0]
	for item in args:
		result = math.gcd(result, item)
	return result

def LCM(a, b):
	return a * b // math.gcd(a, b)

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, sqrt(n)):
		if n % i == 0:
			return False
	return True

def check(a, b, n):
	return a ** 2 + b ** 2 + gcd(a, b) ** 2 + LCM(a, b) ** 2 == n

def count(hcf, n):
	product = n // (hcf * hcf)
	c = 0
	for i in range(2, sqrt(product)):
		if product % i == 0:
			(d1, d2) = (i, product // i)
			(a, b) = (math.sqrt(d1 - 1), math.sqrt(d2 - 1))
			if a == int(a) and b == int(b):
				if check(int(a) * hcf, int(b) * hcf, n):
					if a == b:
						c += 1
					else:
						c += 2
	return c

def solve():
	n = int(input())
	product = []
	i = 1
	while i * i <= n:
		if n % (i * i) == 0:
			product.append(i)
		i += 1
	c = 0
	for item in product:
		c += count(item, n)
	print(c)
t = int(input())
for tt in range(t):
	solve()


import math
from math import gcd
for _ in range(int(input())):
	n = int(input())
	cnt = 0
	t = math.sqrt(n)
	dp = []
	if t == math.floor(t) and n % 2 == 0:
		cnt = 1
	for i in range(2, math.ceil(t)):
		j = n - i * i
		q = math.sqrt(j)
		if q == math.floor(q):
			dp.append([i, q])
	for i in range(len(dp)):
		k = dp[i][0]
		for x in range(1, math.ceil(k / 2)):
			r = math.gcd(x, k - x)
			temp = x * (k - x) / r - r
			if temp == dp[i][1]:
				cnt = cnt + 2
	print(cnt)


from math import gcd

def square_part(n):
	ret = n
	p = 2
	while p ** 2 <= n:
		if n % p == 0:
			num_factors_of_p = 0
			while n % p == 0:
				n //= p
				num_factors_of_p += 1
			if num_factors_of_p % 2 == 1:
				ret //= p
		p += 1
	if n > 1:
		ret //= n
	return ret

def isqrt(n: int) -> int:
	assert n >= 0, 'sqrt works for only non-negative inputs'
	if n < 2:
		return n
	small_cand = isqrt(n >> 2) << 1
	large_cand = small_cand + 1
	if large_cand * large_cand > n:
		return small_cand
	else:
		return large_cand

def is_square(n):
	return n > 0 and isqrt(n) ** 2 == n

def num_good_factorizations(n, verbose=False):
	ret = 0
	for k in range(1, isqrt(n) + 1):
		if n % k == 0 and is_square(k - 1) and is_square(n // k - 1):
			a = isqrt(k - 1)
			b = isqrt(n // k - 1)
			if gcd(a, b) == 1:
				ret += 1
				if k ** 2 != n:
					ret += 1
	return ret

def solution(n):
	n_square_part = square_part(n)
	ret = 0
	d = 1
	while d ** 4 <= n_square_part:
		if n % d ** 2 == 0:
			ret += num_good_factorizations(n // d ** 2)
			if d ** 4 != n_square_part:
				d_partner_sq = n_square_part // d ** 2
				ret += num_good_factorizations(n // d_partner_sq)
		d += 1
	return ret
for _ in range(int(input())):
	print(solution(int(input())))


import sys
import os
import math
from collections import *
import bisect
from heapq import *
from itertools import permutations, combinations
if os.path.exists('input.txt') and os.path.exists('output.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline

def lcm(a, b):
	k1 = math.gcd(a, b)
	k2 = a * b
	return k2 // k1

def inp():
	return map(int, input().strip().split(' '))

def lis():
	return list(inp())
mod = 998244353

def prim(n):
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True

def dfs(adj, vis, u, l):
	vis[u] = 1
	l.add(u)
	for i in adj[u]:
		if vis[i] == 0:
			dfs(adj, vis, i, l)
mod = 10 ** 9 + 7
ma = 1002
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def dfs(i, j, arr, vis, n, m):
	vis[i][j] = 1
	for x in range(4):
		mx = i + dx[x]
		my = j + dy[x]
		if mx >= 0 and mx < n and (my >= 0) and (my < m) and (vis[mx][my] == 0):
			if arr[i][j] >= arr[mx][my]:
				dfs(mx, my, arr, vis, n, m)

def dfs(a, vis, node, c):
	vis[node] = 1
	c[0] += 1
	if vis[a[node]] == 0:
		dfs(a, vis, a[node], c)
mod = 998244353
ma = 2 * (10 ** 5 + 1)
mod = 10 ** 9 + 7

def f(n):
	if n % 4 == 0:
		return n
	if n % 4 == 1:
		return 1
	if n % 4 == 2:
		return n + 1
	return 0

def dfs(node, par, adj, dp, v):
	dp[node] = 1
	for i in adj[node]:
		if i[0] != par:
			dfs(i[0], node, adj, dp, v)
			dp[node] += dp[i[0]]

def dfs1(node, par, adj, dp, v):
	for i in adj[node]:
		if i[0] != par:
			if i[1] == 1:
				v.append(dp[i[0]])
			else:
				dfs1(i[0], node, adj, dp, v)
l = []
for i in range(1, 2 ** 9 + 1):
	l.append(int(bin(i)[2:]))

def finv(p, q):
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p

def pal(s):
	n = len(s)
	for i in range(n):
		if s[i] != s[n - 1 - i]:
			return False
	return True

def f(n):
	res = 2
	while res * res <= n:
		if n % res == 0:
			return False
		res += 1
	return True

def pal(s):
	n = len(s)
	for i in range(n):
		if s[i] != s[n - 1 - i]:
			return False
	return True
mod = 10 ** 9 + 7

def f(n):
	res = 0
	s = bin(n)[2:]
	for i in s:
		res += int(i) & 1
	return res

def solve():
	n = int(input())
	s = set()
	i = 1
	while i <= math.sqrt(n) + 1:
		if n % i == 0:
			s.add(i)
			s.add(n // i)
		i += 1
	l = []
	for i in s:
		g = 1
		while g * g < i:
			at = i - g * g
			atc = math.sqrt(at)
			if atc * atc == at:
				if atc % g == 0:
					l.append([int(atc), g])
			g += 1
	l1 = []
	for i in range(len(l)):
		k = n // (l[i][0] ** 2 + l[i][1] ** 2)
		bt = (k - 1) * l[i][1] ** 2
		btc = math.sqrt(bt)
		if btc * btc == bt:
			lc = l[i] + [int(btc)]
			l1.append(lc)
	ans = 0
	for i in l1:
		(a, b, g) = (i[0], i[2], i[1])
		if a < 1 or b < 1 or math.gcd(a, b) != g:
			continue
		tmp = a * a + b * b + g * g + a * a * b * b // (g * g)
		if tmp == n:
			ans += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


MAX = 10 ** 10
MAXsqrt = 10 ** 5
primes = [2]
is_prime = [True] * (1 + MAXsqrt)

def gcd(a, b):
	if b > a:
		(b, a) = (a, b)
	if b == 0:
		return a
	return gcd(b, a % b)

def sieve(is_prime, primes):
	for i in range(len(is_prime)):
		if is_prime[i]:
			p = 2 * i + 3
			primes.append(p)
			for j in range(3 * p, 1 + MAXsqrt, 2 * p):
				is_prime[(j - 3) // 2] = False

def sqrt_floor(n):
	left = 1
	right = n
	if n < 2:
		return n
	while left <= right:
		m = (left + right) // 2
		if m * m < n:
			left = m + 1
		elif m * m > n:
			right = m - 1
		else:
			break
	if m * m > n:
		return m - 1
	else:
		return m

def get_prime_fac(n, primes):
	pdt = n
	prime_fac = []
	limit = sqrt_floor(n)
	for p in primes:
		a = 0
		while pdt % p == 0:
			pdt = pdt // p
			a = a + 1
		if a > 0:
			prime_fac.append((p, a))
		if pdt == 1 or p > limit:
			break
	if pdt > 1:
		prime_fac.append((pdt, 1))
	return prime_fac

def get_all_divs(n, prime_fac, end):
	x = []
	(p, exp) = prime_fac[end - 1]
	pdt = 1
	for i in range(exp + 1):
		x.append(pdt)
		pdt = pdt * p
	if end == 1:
		return x
	y = get_all_divs(n, prime_fac, end - 1)
	ans = []
	for xx in x:
		for yy in y:
			ans.append(xx * yy)
	return ans

def is_sq_1(n):
	s = sqrt_floor(n)
	if s * s + 1 == n:
		return True
	else:
		return False

def get_sq_1_divs(n, primes):
	arr = get_prime_fac(n, primes)
	divs = get_all_divs(n, arr, len(arr))
	ans = []
	for d in divs:
		if is_sq_1(d):
			ans.append(d)
	return ans

def is_sq(n):
	s = sqrt_floor(n)
	return s * s == n

def check_div_sq(n, x, y):
	gsq = n / x / y
	return int(gsq) == gsq and is_sq(gsq)
t = int(input())
sieve(is_prime, primes)
for ti in range(t):
	n = int(input())
	ans = 0
	arr = get_sq_1_divs(n, primes)
	for (i, x) in enumerate(arr):
		for y in arr[i:]:
			if check_div_sq(n, x, y):
				rx = sqrt_floor(x - 1)
				ry = sqrt_floor(y - 1)
				if gcd(rx, ry) == 1:
					if x == y:
						ans = ans + 1
					else:
						ans = ans + 2
					g = sqrt_floor(n / x / y)
	print(ans)


import math
from math import gcd, sqrt

def lcm(a, b):
	return abs(a * b) // gcd(a, b)

def perfect_square(x):
	return x ** 0.5 % 1 == 0

def get_factors(n):
	factors = []
	i = 1
	while i * i <= n:
		if n % i == 0:
			factors.append(i)
			if n // i != i:
				factors.append(n // i)
		i += 1
	return factors

def sum_of_perfect_squares(x):
	pairs = []
	for j in range(int(math.sqrt(x / 2)), 1 + int(math.sqrt(x - 1))):
		i2 = x - j * j
		i = int(math.sqrt(i2))
		if i * i == i2 and i > 0:
			pairs.append([i, j])
	return pairs

def check(a, b, n):
	if (a + b) ** 2 + (lcm(a, b) - gcd(a, b)) ** 2 == n:
		return True
	return False

def main():
	for _ in range(int(input())):
		n = int(input())
		factors = get_factors(n)
		factors.remove(1)
		ans = 0
		possible_pairs = set()
		for x in factors:
			if perfect_square(x - 1):
				square_pairs = sum_of_perfect_squares(n // x)
				for pair in square_pairs:
					a = pair[0]
					g = pair[1]
					b = int(sqrt((x - 1) * g ** 2))
					possible_pairs.add((a, b))
					(a, g) = (g, a)
					b = int(sqrt((x - 1) * g ** 2))
					possible_pairs.add((a, b))
		for pair in possible_pairs:
			if check(pair[0], pair[1], n):
				ans += 1
		print(ans)
main()


from math import gcd, sqrt

def lcm(a, b):
	return abs(a * b) // gcd(a, b)

def perfect_square(x):
	return x ** 0.5 % 1 == 0

def get_factors(n):
	factors = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			if n / i == i:
				factors.append(i)
			else:
				factors.append(i)
				factors.append(n // i)
	return factors

def sum_of_perfect_squares(x):
	pairs = []
	s = {}
	i = 1
	while i * i <= x:
		s[i * i] = 1
		if x - i * i in s.keys():
			pairs.append([int(sqrt(x - i * i)), i])
		i += 1
	return pairs

def check(a, b, n):
	if (a + b) ** 2 + (lcm(a, b) - gcd(a, b)) ** 2 == n:
		return True
	return False

def main():
	for _ in range(int(input())):
		n = int(input())
		factors = get_factors(n)
		ans = 0
		possible_pairs = set()
		for x in factors:
			f1 = x
			f2 = n // x
			if perfect_square(f1 - 1):
				square_pairs = sum_of_perfect_squares(f2)
				for pair in square_pairs:
					a = pair[0]
					g = pair[1]
					b = int(sqrt((f1 - 1) * g ** 2))
					possible_pairs.add((a, b))
					(a, g) = (g, a)
					b = int(sqrt((f1 - 1) * g ** 2))
					possible_pairs.add((a, b))
		for pair in possible_pairs:
			if check(pair[0], pair[1], n):
				ans += 1
		print(ans)
main()


from math import gcd, sqrt, floor, ceil

def is_perfect_square(x):
	return ceil(sqrt(x)) == floor(sqrt(x))

def main():
	for _ in range(int(input())):
		n = int(input())
		pairs = set()
		ans = 0
		for j in range(2, int(sqrt(n)) + 1):
			if n % j == 0:
				(f1, f2) = (j, n // j)
				if is_perfect_square(f1 - 1):
					s = {}
					i = 1
					while i * i <= f2:
						s[i * i] = 1
						if f2 - i * i in s.keys():
							a = i
							g = int(sqrt(f2 - i * i))
							b = int(sqrt(f1 - 1)) * g
							if a * a + b * b + gcd(a, b) * gcd(a, b) + a * b // gcd(a, b) * (a * b // gcd(a, b)) == n:
								if (a, b) not in pairs:
									ans += 1
								pairs.add((a, b))
							(a, g) = (g, a)
							b = int(sqrt(f1 - 1)) * g
							if a * a + b * b + gcd(a, b) * gcd(a, b) + a * b // gcd(a, b) * (a * b // gcd(a, b)) == n:
								if (a, b) not in pairs:
									ans += 1
								pairs.add((a, b))
						i += 1
				(f1, f2) = (f2, f1)
				if is_perfect_square(f1 - 1):
					s = {}
					i = 1
					while i * i <= f2:
						s[i * i] = 1
						if f2 - i * i in s.keys():
							a = i
							g = int(sqrt(f2 - i * i))
							b = int(sqrt(f1 - 1)) * g
							if a * a + b * b + gcd(a, b) * gcd(a, b) + a * b // gcd(a, b) * (a * b // gcd(a, b)) == n:
								if (a, b) not in pairs:
									ans += 1
								pairs.add((a, b))
							(a, g) = (g, a)
							b = int(sqrt(f1 - 1)) * g
							if a * a + b * b + gcd(a, b) * gcd(a, b) + a * b // gcd(a, b) * (a * b // gcd(a, b)) == n:
								if (a, b) not in pairs:
									ans += 1
								pairs.add((a, b))
						i += 1
		print(ans)
main()