1365: 高次方的尾数

Memory Limit：128 MB Time Limit：2.000 S Judge Style：Text Compare Creator：
Submit：16 Solved：8

Description

在被广泛采用的公开密钥体制的加密和解密计算过程中，求(x的y次方)除以m的余数是一项基本运算。在此，给定x,y,k，求x的y次方的最后k位数。

不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!

Input

第一行包含一个整数n(1≤n≤100),表示测试用例的个数。 每个测试用例的输入有一行，整数x,y,k。其中,0＜x≤1000,0≤y≤1000; 0＜k≤4;

Output

对每个测试用例输出一行。输出x的y次方的最后k位数（忽略前导0）。

Sample Input Copy 

2
2 10 3
10 1000 4

Sample Output Copy 

24
0

HINT

注意：高次方的结果会超过32位二进制整数的表示范围。

Source/Category