Hệ thống phòng thủ của Trái Đất tạo ra một dãy số tự nhiên vô hạn: \(1, 2, 3, 4, 5, 6, \ldots\)

Do bị nhiễm virus, một số phần tử trong dãy bị loại bỏ nếu thỏa mãn ít nhất một trong hai điều kiện:

• Số đó chia hết cho \(A\);
• Số đó có chữ số tận cùng bằng \(B\).

Các số còn lại được gọi là các số sống sót. Chúng giữ nguyên thứ tự ban đầu và tạo thành một dãy mới.

Yêu cầu: Cho số nguyên dương \(N\), hãy tìm số sống sót ở vị trí thứ \(N\) (đánh số từ \(1\)).

Input

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 10^{12}\)).
• Dòng 2: Số nguyên \(A\) (\(1 \le A \le 200\)).
• Dòng 3: Số nguyên \(B\) (\(0 \le B \le 9\)).

Output

• In ra một số nguyên duy nhất là số sống sót ở vị trí thứ \(N\).

Example

5
3
3

8

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(N \le 10^6\).
• Subtask \(2\) (\(40\%\) số điểm): Không có ràng buộc bổ sung.