Migrated from Lutece 167 a ^ b

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

求$a$的$b$次方后四位。

Input

输入的第一行是$T$（不超过$1000$）。$T$表示测试部分的个数，每一部分都要求单独计算并按照要求输出结果。

接下来是每个测试部分。第一行给出$a$, $b$，$0 < a,b\leq 1000000000$。

Output

对于每个测试部分，请输出每个问题的正确答案的最后四位，如果不足四位请前面补$0$。

Samples

2
2 1
3 10

0002
9049

Resources

zhymaoiing