A. Madoka and Strange Thoughtstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputMadoka is a very strange girl, and therefore she suddenly wondered how many pairs of integers (a, b) exist, where 1 \leq a, b \leq n, for which \frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)} \leq 3.In this problem, \operatorname{gcd}(a, b) denotes the greatest common divisor of the numbers a and b, and \operatorname{lcm}(a, b) denotes the smallest common multiple of the numbers a and b.InputThe input consists of multiple test cases. The first line contains a single integer t (1 \le t \le 10^4) — 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 \le n \le 10^8).OutputFor each test case output a single integer — the number of pairs of integers satisfying the condition.ExampleInput
612345100000000Output
1
4
7
10
11
266666666
NoteFor n = 1 there is exactly one pair of numbers — (1, 1) and it fits.For n = 2, there are only 4 pairs — (1, 1), (1, 2), (2, 1), (2, 2) and they all fit.For n = 3, all 9 pair are suitable, except (2, 3) and (3, 2), since their \operatorname{lcm} is 6, and \operatorname{gcd} is 1, which doesn't fit the condition.
612345100000000
1 4 7 10 11 266666666 
['math', 'number theory', '*800']