DCEPC204 - Unlock it !

Vaibhav loves playing with numbers. To enjoy his summer holidays he decides to join the group "number players" of his school. He decides to visit the group hall. At the gate he finds a lock and a paper. The gate can only be unlocked by solving the puzzle written on the paper. Vaibhav is stuck with his puzzle, help him in solving it.

Here is the puzzle description:

Given a sequence F(N)

F(0) = 1
F(1) = 1
F(2) = 1
F(n) = product of all odd primes less than or equal to n (for n<=10)
F(n) = (2^(n/4)) * F(n/5)* F(n/10)      (for n>10)

For every fraction, a ceil value is taken for evaluation.

For eg. F(11)=2^ceil(11/4) * F(ceil(11/5)) * F(ceil(11/10))  = 2^3 * F(3) * F(2) = 24

Given N. Find the max value of (a^b)%mod such that a and b satisfies the relation gcd(a,b) = F(N).

Gcd : Greatest common divisor

Input

First line gives T, total number of test cases.

Next T line gives number N

Output

For each test case, print the desired value on a new line

Constraints

T<=10

N<=10^6

mod = 10^9.

NOTE: a must be <= 5*F(n) and b must be <=5*F(n), a can be equal to b and mod=10^9

Example

Input:
1
2

Output: 1024

Added by:dce coders
Date:2012-02-26
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem

hide comments
2020-07-01 08:31:04 suhash
a = f(n), b = 0 satisfy the constraints of the problem. However, this gives WA. Please clarify in the description that b > 0 (cost me several WA). I see now in the comments that someone already mentioned this.
2014-03-28 21:32:43 SanchitK
please give some more test cases so that i can check if my logic is correct or not
2013-11-11 16:12:30 abdou_93
@dce coders..
Can you give me one n for which my code fails? Please

Edit: found it . :)

Last edit: 2013-11-11 16:25:55
2013-07-06 13:57:07 Gitu
An Awesome Trick Question (Y)
2012-06-07 11:59:28 :D
Fun "trick" problem.
2012-04-26 06:09:30 The Raven
b can not be 0 apparently, even though gcd(F[n],0) = F[n]
2012-04-05 08:27:27 numerix
@problemsetter: Can you give me one n for which my code fails?

>> n=95. don't expect me to tell you the answer coz that would be a give away :)

Last edit: 2012-04-15 10:47:43
2012-03-31 11:07:21 dce coders
@Alex : answer will be 625.
We want the max value possible after mod is taken
2012-03-25 00:22:59 Alex Anderson
Supposing mod were 1000, would the answer on input N = 2 be 625 or 24? That is, do you want the maximum value of (a^b), and then that value returned modulo mod, or do you want the maximum value which might be returned modulo mod?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.