Leading and Trailing

You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of n^k.

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

Each case starts with a line containing two integers: n (2 ≤ n < 2³¹) and k (1 ≤ k ≤ 10⁷).

For each case, print the case number and the three leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that n^k contains at least six digits.

5
123456 1
123456 2
2 31
2 32
29 8751919

Case 1: 123 456
Case 2: 152 936
Case 3: 214 648
Case 4: 429 296
Case 5: 665 669