Naruto and Jiraiya

All submissions for this problem are available.
Jiraiya took Naruto to a forest in the Leaf Village for his training. The forest had N trees indexed from 1 to N each of which has some amount of Chakra in it.
The amount of chakra in the i^{th} tree is the number of fibonacci numbers which are less than the i^{th} fibonacci number and are coprime to the i^{th} fibonacci number. Fibonacci numbers are defined as :
F_{1} = 1,
F_{2} = 1 and
F_{i} = F_{i1} + F_{i2} ∀ i ≥ 3.
For example, the 1st 5 fibonacci numbers are 1, 1, 2, 3, 5, so strength of the first 5 trees are as follows :
Amount of Chakra of 1^{st} Tree = 0 as there are no fibonaccci numbers less than 1,
Amount of Chakra of 2^{nd} Tree = 0 as there are no fibonaccci numbers less than 1,
Amount of Chakra of 3^{rd} Tree = 2 as the 1st 2 fibonacci numbers 1 and 1 are less than the 3rd fibonacci number and also coprime to the 3rd fibonacci number,
Amount of Chakra of 4^{th} Tree = 3 as the 1st 3 fibonacci numbers 1, 1 and 2 are less than the 4th fibonacci number and also coprime to the 4th fibonacci number and
Amount of Chakra of 5^{th} Tree = 4 as the 1st 4 fibonacci numbers 1, 1, 2 and 3 are less than the 5th fibonacci number and also coprime to the 5th fibonacci number.
There is a connection between each pair of trees that have the same amount of chakra. For example, say consider any 5 trees named a, b, c, d and e, with the following amount of chakra 5, 5, 6, 5 and 6 respectively, then there are following connections :
between trees a and b, between trees a and d, between trees b and d and between trees c and e.
In the training, Jiraiya asked Naruto to destroy all existing connections between the trees. Now before Naruto starts destroying the connections with his Rasengan, he wants to know the number of existing connections. So, given the number of trees, calculate the number of connections that Naruto has to destroy.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
Each test case consists of a single line of input consisting of a single integer N denoting the number of trees.
Output
For each test case, output a single integer on a new line denoting the answer to the problem.
Constraints
 1 ≤ T ≤ 10^{6}
 1 ≤ N ≤ 10^{6}
Information to Score Partial Points
 For 5% of the score, it is guaranteed that T,N ≤ 10.
 For further 5% of the score, it is guaranteed that T,N ≤ 100.
 For further 15% of the score, it is guaranteed that T,N ≤ 5000.
 For the rest of the 75% of the score, no extra guarantees. That is, T,N ≤ 10^{6}.
Example
Input: 3
1
6
8 Output: 0
2
3
Explanation
The number of connections for a single tree is 0, for 6 trees is 2 and for 8 trees is 3.
Author:  mohitbindal644 
Tags  mohitbindal644 
Date Added:  16022018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions