Cho 2 số nguyên tố \(a\) và \(b\) với \(a ≠ b\); \(b ≠ 2\) và \(b ≠ 5\). Khi thực hiện chia \(a:b\) thì được một số \(x\) là thập phân vô hạn tuần hoàn.

Yêu cầu: Cho trước số nguyên dương \(n (n ≤ 10^{16})\). Hãy tìm chữ số thứ \(n\) sau dấu phẩy của số \(x\).

Dữ liệu vào:

• Dòng thứ nhất chứa số nguyên tố \(a (a ≤ 1000)\).
• Dòng thứ hai chứa số nguyên tố \(b(b ≠ a;b ≠ 2;b ≠ 5;b ≤ 1000).\)
• Dòng thứ ba chứa số nguyên dương \(n (n ≤ 10^{16}).\)

Kết quả:

• Ghi ra một chữ số thứ \(n\) sau dấu phẩy của số \(x\).

Ví dụ

Input

5
7
15

Output

4

Giải thích

• \(x = 5 : 7 = 0,71428571428571\)4\(285…\) Chữ số thứ \(15\) sau dấu phẩy của số \(x\) là chữ số \(4\).