DCEPC12G  G Force
Prime(n) is defined as number of primes less than equal to n.
Totient(n) is defined as the number of positive integers less than or equal to n that are relatively prime to n.
F(n) = Prime(n) – Totient(n)
and we don’t like negative values, so if F(n) < 0, consider it as 0.
G(n) = Totient(n) ^ (Factorial (F(n)))
You are given a number n. You have to output G(n) % 10^9+7.
Input
First line consists of T, the number of test cases.
Each of the next T lines contains one integer n.
Output
Output T lines each line containing the value of function G(n) % 10^9+7
Constraints
1<=T<=100
1<=n<=10000000
Example
Input: 1
2 Output: 1
hide comments
Francky:
20160628 14:30:24
N vs n ; fixed.


Piyush Kumar:
20160628 10:05:47
This is a good number theory implementation easy problem :) ! Last edit: 20160628 10:06:24 

[Lakshman]:
20151014 19:11:23
@sarvesh_19: can you please delete your comment. Please admin delete the below comment. Thanks 

I know nothing:
20141016 15:35:28
thanks Lakshman for ur comment i got my silly mistake 

[Lakshman]:
20141015 18:42:29
@I know nothing your output for 1,2,30 is correct after that all are incorrect(IDEONE output). 

[Lakshman]:
20141015 18:21:06
@LeppyR64 Yes. 

LeppyR64:
20141015 17:42:02
Is n the same as N? 

anurag garg:
20140107 20:04:53
very good question dce coders.... 
Added by:  dce coders 
Date:  20131207 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  C CSHARP C++ 4.3.2 CPP C99 HASK JAVA PASGPC PASFPC PYTHON PYTHON3 PY_NBC 