IITKWPCM - Coprime Again

no tags 

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/


hide comments
[Lakshman]: 2014-12-19 15:28:15

Finally on top.

Last edit: 2014-12-19 17:01:40
Mitch Schwartz: 2014-12-07 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.

Reply from kewlcoder -> Ok Mitch! got your point. Thanks !

Last edit: 2014-12-07 09:35:02
bourne: 2014-12-07 06:49:49

I suppose the answer for n=1 is 0. Can you please confirm?


Added by:praveen123
Date:2013-08-06
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge