As You had known up to now that Feluda is very good in mathematics, Now he decided to understand the properties of coprime numbers. Two numbers are called coprime if greatest common divisor of those numbers is 1. One day Feluda was reading mysterious book in which he found this problem.

For a given positive integer n, Find out product of all the numbers from 1 to n excluding those which are not coprime to n. As this product can grow very large and Feluda being a small child gets scared from large numbers. Hence he wants that you should output the product modulo n.

Help little Feluda to solve this problem.

Input

T : number of test cases. (T >= 1 and T <= 10^4)

For next T lines, you are given an integer n such that 1 <= n <= 10^18.

Output

For each test case, output one line as stated in the problem statement.

Example

Input:
2
2
5

Output:
1
4

For those who are getting TLE and want to solve easier version. Please go to http://www.spoj.com/problems/IITKWPCQ/