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 ≤ 109). 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 2 55 56 Sample Output Case 1: 120 Case 2: 720