The story to this problem has trailed off.

Given integers n, m, and k, compute the real number n^−m (also known as 1/n^m) and write it as a decimal number in base 10. You can assume that it won’t be a repeating decimal – it can be written with finitely many digits followed by infinite zeros. Print the trailing k digits.

Input

The input contains multiple testcases. Their number 1 ≤ T ≤ 15 is in the first line.

Each test case is a single line containing three integers: n, m and k. (1 ≤ n ≤ 10⁹, 1 ≤ m ≤ 10⁵, 1 ≤ k ≤ 9)

It is guaranteed that n^−m is not a repeating decimal.

Output

Print the last k digits of n^−m after which there are only infinite zeros.

If there are less than k digits after the decimal point, do not print the decimal point. You must always print all k digits, even if your output has leading zeros.

Examples

Input:

2
2 3 2
2 3 5

Output:

25
00125

2⁻³ = 0.125, so the last two digits are 25.

2⁻³ = 0000.1250000. Ignoring the infinite zeros at the end and the decimal point, the last 5 digits are 00125.