As You had known upto now that Feluda is very good in mathematics. Now he has 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 the 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 by 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. (1 <= 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