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 bi and contains exactly i mangoes. The number of mangoes in bi is denoted by mi and m_i = i. Let ti denotes the type of mangoes in box bi (ti is either "real" or "fake"). He can choose any box bi (i <= N-2), but he doesn't know if the box contains "real" mangoes or "fake" mangoes i.e. type of box bi.

The type of mangoes in bi depends on the number of mangoes in boxes bi, bi+1, bi+2 i.e. {mi, mi+1, mi+2}. Mangoes in box bi are "real" if for each pair of numbers taken from set {mi, mi+1, mi+2}, Greatest common divisor(GCD) equals 1. Otherwise, "fake". Note that ti is not defined for i = N-1 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

Added by:Gopal Rander
Date:2013-02-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode '13

hide comments
2014-07-22 14:39:22 Luv Karakoti
:D My 50th classical ^_^
2014-07-02 20:09:01 Michael Scofield
1st tym AC in first attempt. :D
2014-06-27 09:03:53 Diksha Jaiswal
1 go...easy...:)
2014-06-25 18:17:09 jetpack
find a pattern..that's all!:)
O(1).




Last edit: 2014-06-25 18:50:42
2014-05-27 23:03:14 pvkcse
Getting internal error...!!!can't get what it is...!!!

Guess worked after several WA...!!!

Last edit: 2014-06-08 22:31:16
2014-05-21 20:15:56 Divyank Duvedi
CakeWalk!!!
2014-05-12 19:02:27 drfgthyjuikjhgftrd
i am getting sigsegv error after running judge 8 pls help :( :(
2013-12-15 13:20:55 Shadow_Walker
Nice prob .. realised its simplicity only after using pen n paper.. Shortest code :)
2013-10-16 20:03:12 Chandan Mittal
100th classical AC :)
2013-09-15 06:17:16 Abhishek Gupta
AC :)

Last edit: 2013-10-25 15:28:19
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.