Maria and her number!

Time: 1 s
Memory: 256 MB

Maria is a student of Metropolitan University, she's a kind & lovely girl. She has an obsession with numbers,recently one of her friends gave her a number which is equal to the factorial of some Integer n.

As mentioned Maria is kind, so she loves to share things with her friends. Now she is thinking she wants to share a number x which is the greatest divisor of n! and x < n!

But now she is busy with some other work,and as you're one of the best programmers of Metropolitan University she needs your help to find out the number x which is the greatest divisor of n! and x < n!.

Note N! = 1 * 2 * 3 * .........*N-1 * N
Since the number x might be too large, please print it modulo \(10^9\)+7.

Input

The first line contains a single integer T — the number of test cases.
The following T line contains a single integer N– the N! is the number she received as a gift.

Constraint

T(1 <= T <= \(10^5\))
N(2 <= N <= \(10^6\))

Output

For each case, print the case number,the number x modulo 1e9+7.

Examples

Input	Output
3 2 3 5	Case 1: 1 Case 2: 3 Case 3: 60

Notes

In the first test case: n = 2, so 2! = 2*1 = 2 The greatest divisor of 2 less than 2 is 1 so the answer is 1.

Problem ID	218
Time Limit	1000 ms
Memory Limit	262144 KB
Moderators	mhmuhim , Alom_Shanto , Royboy01

You need to Login or Registration for submit your solution