## 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:

``22 3 22 3 5``

Output:

``2500125``

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. 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