Cho phân số ~P/Q~, tiến hành biểu diễn phân số trong hệ cơ số thập phân, sau khi loại bỏ dấu chấm thập phân (dấu ngăn cách giữa phần nguyên và phần thực) ta nhận được một xâu số có độ dài vô hạn. Đánh số các kí tự của xâu bắt đầu từ 1, để khảo sát phân số, với một xâu mẫu người ta muốn tìm vị trí xuất hiện thứ ~k~ của ~X~ trong ~S~.

Yêu cầu: Cho ~P, Q, k~ và xâu ~X~, hãy xác định vị trí xuất hiện thứ ~k~ của ~X~ trong ~S~, trong đó ~S~ là biểu diễn của phân số ~P/Q~ trong hệ cơ số thập phân sau khi loại bỏ dấu chấm ngăn cách giữa phần nguyên và phần thực.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~P, Q, k~ (~0 < P, Q, k \le 10^6~);
• Dòng thứ hai chứa một xâu số ~X~ có độ dài không vượt quá ~10^5~.

Output

• Ghi ra một số là vị trí xuất hiện thứ ~k~ của ~X~ trong ~S~, nếu không tồn tại ghi số 0.

Sample Input 1

3 7 2
2

Sample Output 1

8

Sample Input 2

3 5 2
00

Sample Output 2

3