MANGOES  Real Mangoes for Ranjith
Ranjith is very fond of mangoes. One fine sunny day, he goes to market to get some mangoes. In the market place, he finds N boxes (indexed from 1 to N), filled with mangoes kept infront of him. Each box indexed i is denoted by b_{i} and contains exactly i mangoes. The number of mangoes in b_{i} is denoted by m_{i} and m_i = i. Let t_{i} denotes the type of mangoes in box b_{i} (t_{i} is either "real" or "fake"). He can choose any box b_{i} (i <= N2), but he doesn't know if the box contains "real" mangoes or "fake" mangoes i.e. type of box b_{i}.
The type of mangoes in b_{i} depends on the number of mangoes in boxes b_{i}, b_{i+1}, b_{i+2} i.e. {m_{i}, m_{i+1}, m_{i+2}}. Mangoes in box b_{i} are "real" if for each pair of numbers taken from set {m_{i}, m_{i+1}, m_{i+2}}, Greatest common divisor(GCD) equals 1. Otherwise, "fake". Note that t_{i} is not defined for i = N1 and i = N and assumed to be "fake".
Given N, Ranjith wants to know the total number of "real" mangoes he will get from all boxes. As Ranjith cannot count beyond N, output the result modulo N.
Input
Test File starts with number of test cases  T;
T lines follows, each containing N, number of boxes.
Output
Output T lines Number of "real" mangoes Ranjith gets (modulo N) in each one of the T cases.
Constraints
2 < N <= 10^8
T <= 10000
Example
Input: 2 9 5 Output: 7 4
hide comments
arjun8115:
20180104 20:23:48
finally 200... 

ab_hi_shek111:
20170927 13:33:01
My 200th :) EASY ONE :p 

nadstratosfer:
20170908 07:18:34
Spent more time on deciphering the stupidly convoluted problem statement than on solving.


viratian_070:
20170608 09:03:30
easy one....output for n=2 is 0 

pandu ranga rao:
20161201 19:06:52
Can any one explain answer for n = 3? 

sri:
20161121 16:16:35
"FOR EACH PAIR" of {m1,m2,3} gcd should be 1. 

vineetpratik:
20160624 20:55:32
O(1) no need to find gcd , just observe :) 

roy_24:
20160611 07:43:31
Gcd of 3 consecutive numbers is always 1 !! :o


aloochaat1998:
20151202 13:53:19
piece of cake :) 

Anant Upadhyay:
20150912 08:24:13
easy !! 
Added by:  Gopal Rander 
Date:  20130226 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Bytecode '13 