To write a problem description of a problem is a boring task to me. And this time, I can’t be bothered. :D. So I have nothing to say about this problem. Just do it...

You are given an positive integer N. Your task is to calculate the factorial of N.

Input

The input contains an integer T (1 ≤ T ≤ 1000) number of test cases. Second line input is N (0 < N ≤ 10⁶) that indicates the positive integer.

Output

For each case, print the case number and the result modulo 1000000007. See the sample input/output for exact formatting.

Example

Input:
3
4
7
10

Output:
Case 1: 24
Case 2: 5040
Case 3: 3628800

Problem Setter: Shipu Ahamed, Dept. of CSE
Bangladesh University of Business and Technology (BUBT)