You are given an integer N. You have to count the number of distinct tuples (A, B, C, D) with 1 ≤ A, B, C, D ≤ N such that A \cdot B = C \cdot D. 

Two tuples, say (A, B, C, D) and (E, F, G, H) are considered to be different if at least one of the following conditions hold true: 
A \neq E 
B \neq F
C \neq G
D \neq H.

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

- First line will contain T, number of testcases. Then the testcases follow.
- Each testcase contains a single integer on a new line - N, as described in the problem statement

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

For each testcase, output the answer on a new line - the number of tuples as described in the problem statement.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{6}$

----- Sample Input 1 ------ 
3
3
50
35
----- Sample Output 1 ------ 
15
10950
4831
----- explanation 1 ------ 
Test case $1$:
Following tuples satisfy the given condition:
- (1, 1, 1, 1)
- (1, 2, 2, 1)
- (1, 3, 3, 1)
- (2, 1, 1, 2)
- (2, 2, 2, 2)
- (2, 3, 3, 2)
- (3, 1, 1, 3)
- (3, 2, 2, 3)
- (3, 3, 3, 3)
- (1, 2, 1, 2)
- (2, 1, 2, 1)
- (1, 3, 1, 3)
- (3, 1, 3, 1)
- (2, 3, 2, 3)
- (3, 2, 3, 2)

$A \cdot B = C \cdot D$ holds true for all these tuples.

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory


Solutions:
t = int(input())

def euler_t(n):
	v = []
	for i in range(n):
		v.append(i)
	for i in range(2, n):
		if v[i] == i:
			for j in range(i, n, i):
				v[j] = v[j] // i * (i - 1)
	return v
euler = euler_t(1000010)
for arr in range(t):
	n = int(input())
	ans = 0
	for i in range(1, n + 1):
		t = i
		if i == 1:
			ans += euler[i] * (n // i) * (n // i)
		else:
			ans += euler[i] * (n // i) * (n // i) * 2
	print(ans)