You are currently in charge of a large multinational company. You have many projects in hand. There are N employees currently in your company and all of them have a unique ID, numbered from 1 to N. You want to form a non-empty set of teams of equal size, from these employees, such that each team works under a unique project and each employee works in exactly one team. Your task is to find the number of ways to form such sets of teams. Two ways are different, if the number or size of the teams are different, or if a pair of employees works in the same team in one formation, but works in different teams in another formation. Input The first line of each input contains a single integer T (1 ≤ T ≤ 5000), which denotes the number of test cases. The next T lines contain a single integer N (1 ≤ N ≤ 106). Output For each test case, output the case number, followed by the number of ways to form non-empty sets of equal sized teams from N employees. Since the result can be large, print it modulo 1000000007. See the sample input/output for more clarification. Sample Input 3 1 3 10 Sample Output Case 1: 1 Case 2: 2 Case 3: 1073