ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1268. Little Chu

Time limit: 0.25 second
Memory limit: 64 MB
The favorite occupation of Little Chu is to sleep. Strictly speaking, he is busy with nothing but sleeping. Sometimes he wakes up and than the mankind makes some Great Discovery. For the first time Little Chu woke up K days after his birth. For the second time he woke up K2 after his birth. For the third time — K3 days after his birth. This rule still holds true.
Each time whem Little Chu wakes up he looks at the calendar and remembers what day of week is today. They say that if the day of week will be repeated, than Litle Chu will start crying and his tears will flood the world.
Your task is to make the largest number of the Great Discoveries and maximally to delay the doomsday. Determine when should Little Chu be awaken for the first time if it is known that he can’t sleep more than one week after his birth.

Input

The first line contains integer T (1 ≤ T ≤ 6553) — the number of tests. Each of the next T lines contains integer N (2 < N < 65536) — the number of days in the week. N is prime.

Output

K for each input test.

Sample

inputoutput
4
3
5
7
11
2
3
5
8
Problem Author: Pavel Atnashev
Problem Source: Ural State University championship, October 25, 2003