Summing up Powers

2 seconds
64 MB
Medium Hard
LOJ-1132 Udebug Debug
English

Given N and K, you have to find:

(1K+2K+3K++NK)mod232

Input

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

Each case contains two integers N (1 ≤ N ≤ 1015) and K (0 ≤ K ≤ 50) in a single line.

Output

For each case, print the case number and the result.

Sample

Sample Input Sample Output

3 3 1 4 2 3 3

Case 1: 6 Case 2: 30 Case 3: 36