IITKWPCM  Coprime Again
As You had known upto 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 && 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 Who are going TLE and want to solve easier version. Please go to http://www.spoj.com/problems/IITKWPCQ/
hide comments
[Lakshman]:
20141219 15:28:15
Finally on top. Last edit: 20141219 17:01:40 

Mitch Schwartz:
20141207 07:10:43
@kewlcoder, there is no ambiguity in the problem statement regarding that case, you should be able to know the answer by understanding the problem.


bourne:
20141207 06:49:49
I suppose the answer for n=1 is 0. Can you please confirm? 
Added by:  praveen123 
Date:  20130806 
Time limit:  4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  IITK ACA CSE online judge 