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ỏ phần nguyên và dấu chấm thập phân (dấu ngăn cách giữa phần nguyên và phần thập phân) ta nhận được một xâu số ~S~ có độ dài vô hạn. Đánh số các kí tự của xâu ~S~ bắt đầu từ ~1~, để khảo sát phân số, với một xâu mẫu ~X~ 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ố ~\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.

Dữ liệu:

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

Kết quả: 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~ .

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 ~X~ bằng ~1~;
• 40\% số test khác ứng với ~40 \%~ số điểm của bài thỏa mãn: ~k=1~;
• ~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.

Ví dụ:

Sample Input 1

3 7 2 
2

Sample Output 1

8

Sample Input 2

3 5 2 
00

Sample Output 2

3