Cho số nguyên dương \(n\) và một tập \(S\) gồm các chữ số thập phân \(\{0 \ldots 9\}\). Hãy tìm một số nguyên dương \(m\) thỏa mãn các điều kiện sau đây:

• \(m\) có biểu diễn thập phân chỉ gồm các chữ số trong tập \(S\),
• \(m\) chia hết cho \(n\),
• \(m\) nhỏ nhất có thể.

Input

Vào từ file văn bản LM.INP

• Dòng 1 chứa số nguyên dương \(n \leq 10^6\).
• Dòng 2 chứa không quá \(10\) ký tự liền nhau, mỗi ký tự là một chữ số trong tập \(S\).

Output

Ghi ra file văn bản LM.OUT một dòng duy nhất chứa số \(m\) tìm được. Nếu không tồn tại số \(m\) thỏa mãn các yêu cầu đặt ra thì ghi trên dòng này một số \(0\).

Example

7
24

42

18
14

144

10
1234

0

Nguồn: Thầy Lê Minh Hoàng