Last Digits of a Power

Time Limit	Memory	Input	Output
1 s	64 MB	stdin	stdout

Time Limit

Memory

Input

Output

1 s

64 MB

stdin

stdout

For given positive integers $a$ , $n$ and $k$ , your task is to print the last $k$ digits of the power $a^{n}$ .

Input

First line of input will be a single integer $t$ - the number of testcases.
Each of the next $t$ lines contains three integers $a$ , $n$ and $k$ .

For every testcase print a single line with exactly $k$ characters - the last (rightmost) $k$ digits of $a^{n}$ , including leading zeros.

Input

Output

192
000
0576

$2^{13} = 8192$ , so its last three digits are $192$ . $1 0^{5} = 100000$ ends in three zeros - all three must be printed.

$1 \leq t \leq 1 0^{5}$
$1 \leq a, n \leq 1 0^{9}$
$1 \leq k \leq 9$

This problem was adapted, with permission, from Poslednjih k cifara stepena, authored by Društvo matematičara Srbije and Fondacija Petlja.

Time Limit	Memory	Input	Output
1 s	64 MB	stdin	stdout

For given positive integers $a$ , $n$ and $k$ , your task is to print the last $k$ digits of the power $a^{n}$ .

First line of input will be a single integer $t$ - the number of testcases.
Each of the next $t$ lines contains three integers $a$ , $n$ and $k$ .

For every testcase print a single line with exactly $k$ characters - the last (rightmost) $k$ digits of $a^{n}$ , including leading zeros.

Input

Output

192
000
0576

$2^{13} = 8192$ , so its last three digits are $192$ . $1 0^{5} = 100000$ ends in three zeros - all three must be printed.

$1 \leq t \leq 1 0^{5}$
$1 \leq a, n \leq 1 0^{9}$
$1 \leq k \leq 9$

This problem was adapted, with permission, from Poslednjih k cifara stepena, authored by Društvo matematičara Srbije and Fondacija Petlja.