## 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.

2 < N <= 10^8
T <= 10000

### Example

```Input:
2
9
5

Output:
7
4```