You know Dr. Sheldon cooper!! He is brilliant physicists. He always try to invent new things and establish new theory. Today he has written a new pseudo code for his new theory.

Pseudo code:

{
    take two integers x and n
    let ans := 1
    for i = 1 to n:
        ans := ans * x
    let ans: = ans MODULO (1018+7)
}

But Dr. Sheldon cooper suddenly realized that, this is not optimized code. It takes too much time for providing correct answer. So he needs a better code for his work.

As a programmer you can help Dr. Sheldon cooper. You should write code that gives the correct answer in efficient time.

Input

The first line of the input contains an integer T denoting the number of test cases. Each test case contain two space separated integer x and n. (0 ≤ x, n ≤ 10^18)

Output

For each case, print the case number and the desired answer. And remember that answer should be modulo of (10^18+7).

Sample

Input:
3
2 3
5 3
10 5

Output
Case 1: 8
Case 2: 125
Case 3: 100000

Authored By: Tanvir Hasan Anick