SP17399 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.

First line consists of **T**, the number of test cases. Each of the next **T** lines contains one integer **n**.

Output **T** lines each line containing the value of function G(**n**) % 10^9+7