I think all of you have seen the popular television series Robin Hood. You’ve heard about Robin Hood. He is a brave and kind-hearted man. He loves people very much. He wants to help the poor people. But he is working with Robin Hood team at this moment. So, he is too busy for shooting TV series. Although he’s a star and wants to help the poor, he is not rich as you think. Suddenly he took a decision about robbing a bank. He will rob the World Bank and distribute the money to poor countries. But the problem is how much money a country should be given. Some countries are developed, and some are developing. So, he sets a condition. Every country will be marked by a number (N) that represents countries’ ranks (if a rank is smaller that means those countries are developed or rich enough) and Robin Hood will take a number M randomly to calculate M^^N. Since M^^N can be much bigger, so calculate (M^^N) modulo 1000000007(10⁹+7). And finally he will calculate the sum of divisor of that number. Then he will give the money to that country.

Since Robin Hood is weak in programming. So, he asks for your help.

Input

The first line in the data set is an integer T (1 <= T <= 200) that represents the number of data collections that follow. Each data set contains two integers M, N (1 <= M, N <= 100)

Output

For each test case print the money that Robin Hood can give to the specific country. Since the power of M^^N can be much bigger, (M^^N) modulo 1000000007(10⁹+7). But don’t modulo the final sum of divisor. See sample input and output for exact format.

Example

Input:
3
2 5
14 11
63 60

Output:
Case 1: 63
Case 2: 565976772
Case 3: 1174118400