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 in front 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 ≤ N-2), 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 = 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⁸
T ≤ 10000

Example

Input:
2
9
5

Output:
7
4