Chữ số 0 tận cùng

Cho ba số nguyên dương \(A, B, K\) (\(1 \leq A, B \leq 10^9\), \(1 \leq K \leq 15\)).

Yêu cầu: Hãy tìm số nguyên dương \(C\) nhỏ nhất sao cho tích của ba số \(A, B, C\) có ít nhất \(K\) chữ số \(0\) tận cùng.

Input

• Nhập vào ba số nguyên dương lần lượt theo thứ tự là \(A, B\) và \(K\). Mỗi số viết trên một dòng.

Output

• Đưa ra một số duy nhất là số nguyên dương \(C\) thỏa mãn yêu cầu đề bài.

Example

15
12
2

5

Scoring

• Nếu chương trình chạy đúng những trường hợp \(1 \leq A, B \leq 10^3, 1 \leq K \leq 9\), thí sinh sẽ được \(40\) điểm;

• Nếu chương trình chạy đúng những trường hợp \(1 \leq A, B \leq 10^9, 1 \leq K \leq 15\) thí sinh sẽ được \(100\) điểm