TRAILDIG - Trailing digits

no tags 

The story to this problem has trailed off.

Given integers n, m, and k, compute the real number nm (also known as 1/nm) 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 ≤ 109, 1 ≤ m ≤ 105, 1 ≤ k ≤ 9)

It is guaranteed that nm is not a repeating decimal.

Output

Print the last k digits of nm 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: 2019-12-11 15:52:55

Nice problem! Easy once you understand the logic to solve!

nadstratosfer: 2019-12-01 05:19:15

Enjoyed!

wisfaq: 2019-11-30 20:37:30

Great problem. Thanks.

[Rampage] Blue.Mary: 2019-11-30 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]: 2019-11-30 06:50:02

.

Last edit: 2019-12-16 20:17:52

Added by:Hodobox
Date:2019-11-26
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own problem