无额外样例。

题目描述

给出两个整数 $n, m$, 请你计算 $n^m$.

运算结果可能很大，你只需要输出结果的最高五位和最低五位。

结果不足五位的，前面补 0 凑足五位输出。

多组数据。

输入格式

第一行：一个整数 T，表示数据组数.

接下来 T 行，每行两个整数 n, m.

输出格式

共 T 行，每组数据的答案占一行，分别输出结果的最高五位和最低五位，中间以一个空格隔开。

样例输入

10
1 1234567
2 1234567
1234567890 1
1234567890 2
1234567890 1234567
123456789 1234567
123456789 2333333
123456789 9876543
2147483647 9999999
2147483647 10000000

样例输出

00001 00001
49963 72928
12345 67890
15241 52100
23486 00000
23486 64829
82456 75269
40472 48669
20983 25983
45062 00001

数据范围

$T ≤ 1000, 2 ≤ n < 2^{31}, 1 ≤ m ≤ 10^7$