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 ith tree is the number of fibonacci numbers which are less than the ith fibonacci number and are coprime to the ith fibonacci number. Fibonacci numbers are defined as :-
F1 = 1,
F2 = 1 and
Fi = Fi-1 + Fi-2 ∀ 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 1st Tree = 0 as there are no fibonaccci numbers less than 1,
Amount of Chakra of 2nd Tree = 0 as there are no fibonaccci numbers less than 1,
Amount of Chakra of 3rd 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 4th 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 5th 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.
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.
For each test case, output a single integer on a new line denoting the answer to the problem.
- 1 ≤ T ≤ 106
- 1 ≤ N ≤ 106
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 ≤ 106.
8 Output: 0
The number of connections for a single tree is 0, for 6 trees is 2 and for 8 trees is 3.
|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|
Fetching successful submissions