khann的number theory

khann is a very strange ACMer, and therefore he suddenly wondered how many pairs of integers (a,b) exist, where 1≤a,b≤n   , for which lcm(a,b)gcd(a,b)≤3

In this problem, gcd(a,b)   denotes the greatest common divisor of the numbers a and b, and lcm(a,b)$l$ denotes the smallest common multiple of the numbers a and b

(让大家练练英语

The input consists of multiple test cases. The first line contains a single integer t(1≤t≤104) ）— the number of test cases. Description of the test cases follows.

The first and the only line of each test case contains the integer n (1≤n≤108）））

For each test case output a single integer — the number of pairs of integers satisfying the condition.

6
1
2
3
4
5
100000000

1
4
7
10
11
266666666