J	Musical Chair

Do you know the game "Musical Chair"? It is a very popular game in school function. There are n chairs arranged in the field in a shape of circle. That is, Chair 1 is adjacent to Chair 2, Chair 2 is adjacent to Chair 3 … Chair n is adjacent to Chair 1. You have to color the chairs by one of the k colors so that there are no three consecutive chairs among which two of them contain same color.

Input

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers: n k (1 ≤ n, k ≤ 10⁹).

Output

For each case, print the case number and the number of ways the chairs can be colored maintaining the above restrictions. Since the result can be too large, print the result modulo 34830.

Sample Input	Output for Sample Input
2 5 5 5 6	Case 1: 120 Case 2: 720

---

Problem Setter: Md. Mahbubul Hasan, Special Thanks: Jane Alam Jan, Shahriar Rouf Nafi