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

Input

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 < 231) and k (1 ≤ k ≤ 107).

Output

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 nk contains at least six digits.

Sample Input	Output for Sample Input
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

题意:求n的k次方的前三位和后三位，后三位要补前导零。

求前三位的话：可以设 n^k = x*10^（len-1），len = (int) ( k*log(n) ) ,然后对原式两边同时取对数，就变成了 k*log（n） =  log（x * 10^(len-1) ）= log (x) + log(10 ^ (len-1) ) ，所以x = pow(10,1.0*k*log10(n)-len+1)，有同学就会说 了：“唉？len不就等于k*log(n)吗，跟这个k*log(n)不就消掉了吗”，注意这个pow里的k*log（n）是浮点型的，那个求得的len肯定是个整型，所以不能消掉。

求后三位的话：直接快速幂，对1000取模就好了。

#include<set>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long

using namespace std;


const int maxn = 1e6;
const int mod = 1000;

LL qucikpower(LL x,int k)
{
    LL ans = 1;
    while(k)
    {
        if(k & 1)
            ans = ans*x%mod;
        x = x*x%mod;
        k /= 2;
    }

    return ans;
}

int main(void)
{
    int T,n,k;
    scanf("%d",&T);
    int cas = 1;
    while(T--)
    {
        scanf("%d%d",&n,&k);
        int len = k*log10(n) + 1;
        double t = pow(10,1.0*k*log10(n)-len+1);
        while(t < 100)
            t*=10;
        int x = t;
        int y = qucikpower(n,k);
        printf("Case %d: %d %03d\n",cas++,x,y);
    }
    return 0;
}