Cho phân số \(\frac{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 \(S\) trong \(T\).

Yêu cầu: Cho \(p, q, k\) và xâu \(S\), hãy xác định vị trí xuất hiện thứ \(k\) của \(S\) trong \(T\), trong đó \(T\) là biểu diễn của phân số \(\frac{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ữ liệu vào từ file văn bản FRACT.INP:
  • Dòng đầu tiên chứa ba số nguyên dương \(p, q, k\);
  • Dòng thứ hai chứa một xâu số \(S\) có độ dài không vượt quá \(10^5\).

Output

• Ghi ra file văn bản FRACT.OUT một số là vị trí xuất hiện thứ \(k\) của \(S\) trong \(T\), nếu không tồn tại ghi số \(0\).

Ràng buộc

• Có \(40\%\) số test ứng với \(40\%\) số điểm của bài thỏa mãn: độ dài xâu \(S\) bằng \(1\);
• \(40\%\) số test khác ứng với \(40\%\) số điểm của bài thỏa mãn: \(q \le 10^5\);
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài thỏa mãn: không có ràng buộc nào thêm.

Example

3 7 2
2

8

3 5 2
00

3