MANGOES - Real Mangoes for Ranjith

no tags 

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

hide comments
Divyansh Bajpai: 2015-06-01 17:41:42

shortest code ever! use long long int...pretty simple :)

biswas: 2015-05-31 08:48:58

WTF...gives WA if test cases (t) is not in long long in C.... waste of time

shantanu tripathi: 2015-05-18 08:59:42

should be moved to tutorials!!!!

ASHUTOSH DWIVEDI: 2015-05-11 13:17:12

easy one.......AC :)

[Mayank Pratap]: 2015-03-26 14:47:45

O(1)...Good problem for beginners like me :)

Aditya Kumar: 2015-03-24 16:07:19

O(1)
Green....

kartikay singh: 2015-03-04 21:26:00

Bad Day:(
several WA :silly mistakes

Last edit: 2015-03-04 21:26:23
Abhinandan Agarwal: 2015-01-16 13:54:39

silly mistakes,

ash_cash: 2015-01-13 20:23:46

1 WA due to a silly mistake... !!!!

soumya poddar: 2014-12-25 18:35:23

not able to understand why keep having WA. Done the solution with O(1).
Is it because of output format please help.
----->
sorry overflow issues.

Last edit: 2014-12-26 11:15:35

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