题目描述
在被广泛采用的公开密钥体制的加密和解密计算过程中，求(x的y次方)除以m的余数是一项基本运算。在此，给定x,y,k，求x的y次方的最后k位数。
输入
第一行包含一个整数n(1≤n≤100),表示测试用例的个数。 每个测试用例的输入有一行，整数x,y,k。其中,0＜x≤1000,0≤y≤1000; 0＜k≤4;
输出
对每个测试用例输出一行。输出x的y次方的最后k位数（忽略前导0）。
样例输入 Copy
2
2 10 3
10 1000 4
样例输出 Copy
24
0
提示
注意：高次方的结果会超过32位二进制整数的表示范围。