Given N and K, you have to find:
$$ (1^K + 2^K + 3^K + \dots + N^K) \mod 2^{32} $$
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 |