Distinct Perfect Square Pairs

You are given an integer n and you are required to count the number of distinct pairs (a, b) such that 1 ≤ a, b ≤ n and the product a \times b is a perfect square. Note that a pair (a, b) and (b, a) are considered distinct if a ≠ b.

The answer for each test case should be computed by iterating through all pairs with a ≤ b and, if a*b is a perfect square, counting the pair as one when a = b and two otherwise (to account for both orderings). The solution should use LaTeX format for mathematical expressions, for example, a perfect square is defined as a number x for which \(\sqrt{x} = \lfloor \sqrt{x} \rfloor\).

For example:

• For n = 2: the valid pairs are (1,1) and (1,2) & (2,1) because \(1 \times 1 = 1\) and \(1 \times 2 = 2\) but only \(1\) is a perfect square, so the count is 2.
• For n = 4: the valid pairs yield a count of 6.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each of the following T lines contains a single integer n.

Input is read from standard input (stdin).

outputFormat

For each test case, output the number of distinct pairs (a, b) such that \(1 \leq a, b \leq n\) and \(a \times b\) is a perfect square. Each result should be output on a new line on standard output (stdout).

## sample

3
2
3
4

2
3
6

</p>