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
2018-01-04 20:23:48
finally 200...
2017-09-27 13:33:01
My 200th :) EASY ONE :p
2017-09-08 07:18:34
Spent more time on deciphering the stupidly convoluted problem statement than on solving.

Each box Bi contains i mangoes. They are fake if any pair of numbers in (i, i+1, i+2) has a GCD>1. Find out which boxes up to i=n-2 contain real fruit and print the sum of their contents mod n.
2017-06-08 09:03:30
easy one....output for n=2 is 0
2016-12-01 19:06:52 pandu ranga rao
Can any one explain answer for n = 3?
2016-11-21 16:16:35 sri
"FOR EACH PAIR" of {m1,m2,3} gcd should be 1.
2016-06-24 20:55:32
O(1) no need to find gcd , just observe :)
2016-06-11 07:43:31
Gcd of 3 consecutive numbers is always 1 !! :o
When its even-odd-even, then 2 is not the gcd as 2 does not divide odd number.
I don't understand the test cases.


Last edit: 2016-06-11 07:47:02
2015-12-02 13:53:19
piece of cake :)
2015-09-12 08:24:13 Anant Upadhyay
easy !!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.