Problem Description

D.A., short for Dumbledore's Army, is found by Harry while fighting with Voldemort. In the last battle, the D.A. has contributed greatly to smashing the Death Eater. Before this, Harry Potter had trained them a lot about defensing against the Dark Arts.

For easy recognizing, each of the D.A. has a unique ID, from 1 to N. At ordinary time, they lined up by a certain order. But in Harry’s memory, there was one day they messed up, so he asked them to change their position. At first, he use the magic to remember all pairs, e.g. if the i-th ID is pi, Harry would commit the pair to memory. Then, in each round, he would require the pi-th magician to stand in the i-th place. By doing this again and again, after exactly K round, he found the ID sequence is the same as the original, and what’s more, it’s the first time they all come back!
But unfortunately, Harry can’t remember the ID sequence on that day, so he asks you for help, to calculate the number of permutations fitting this situation.

Input

The first line contains a single integer T, indicating the number of test cases.
Each test case contains two integers, N and K.

Technical Specification

1. 1 <= T <= 50
2. 1 <= N <= 100
3. 1 <= K <= 1 000 000 000

Output

For each test case, output the case number first, then the answer mod 1 000 000 007.

2
1 1
3 3

Case 1: 1
Case 2: 2

Author

iSea@WHU