SP11440 DCEPC604 - Unlock it ! Part 2

Now you all helped Vaibhav solve the puzzle and open the gate last time (although not too much help). But as soon as he opens the gate, there is another puzzle to open the front door. Let’s see whether this time you all are able to help him or not. Fac(n) = no of zeroes in n! Fact(n)= Fac(n)%25+1 F(0)=1 F(1)=1 F(2)=1 F(n) = product of all odd primes less than or equal to n (for n10) **For every fraction , a floor value is taken for evaluation.** **For eg. F(11)=4^fact(11) \* F(floor(11/5)) \* F(floor(11/10)) = 4^3 \* F(2) \* F(1) = 64** 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

First line gives T, total number of testcases. Next T line gives number N

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