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 K² after his birth. For the third time — K³ 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.

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.

K for each input test.