"IT can do almost everything using codes", a Arjun(a CS Student) says to his mathematics' teacher. Mathematics teacher gives a very simple problem to solve using codes but Arjun got stuck. The problem was find out all those pairs of two numbers whose multiplication is divisible by their sum, i.e.

You are given a number Q. Find all pairs (m,n), where m < n && 1 <=m && n <=Q, such that m*n is divisible by m+n.

Being a Techgeek, help Arjun to prove his statement correct.

Input The first line contains a single positive integer T <= 50, the number of test cases. T test cases follow. The only line of each test case contains a positive integer Q <= 10^9.

Output

For each test case, output a single line containing the answer for the corresponding test case. Example

Input:

2

2

15

Output:

0

4

Explanation

In the second test case required pairs are (3, 6), (4, 12), (6, 12) and (10, 15).