TRAILDIG  Trailing digits
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^{9}, 1 ≤ m ≤ 10^{5}, 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^{−3} = 0.125, so the last two digits are 25.
2^{−3} = 0000.1250000. Ignoring the infinite zeros at the end and the decimal point, the last 5 digits are 00125.
hide comments
tsrvineel:
20191211 15:52:55
Nice problem! Easy once you understand the logic to solve! 

nadstratosfer:
20191201 05:19:15
Enjoyed! 

wisfaq:
20191130 20:37:30
Great problem. Thanks. 

[Rampage] Blue.Mary:
20191130 14:43:58
@luckymastermin： both of your tests are invalid. In problem statement it says: "You can assume that it won’t be a repeating decimal – it can be written with finitely many digits followed by infinite zeros. " 

[Lakshman]:
20191130 06:50:02
. Last edit: 20191216 20:17:52 
Added by:  Hodobox 
Date:  20191126 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  own problem 