Với mỗi số nguyên dương, chúng ta có thể nhận được một số không âm đặc biệt bằng cách nhân các chữ số của nó với nhau. Việc này định nghĩa một hàm F với ý nghĩa F(x) là tích các chữ sốcủa x, ví dụ F(25) = 10.Để làm hàm F đặc sắc hơn, anh Kiên quyết định cho phép tính hàm F ở hệ cơ số khác. Ví dụ, ở hệ cơ số 3, số 23 được viết dưới dạng 212, do đó ~ F_3 ~(23) = 2 ∗ 1 ∗ 2 = 4 . Anh Kiên muốn nhờ bạn giúp anh ấy giải quyết bài toán sau: Cho cơ số B và một số nguyên dương N, tìm số nguyên dương X nhỏ nhất thỏa mãn FB(X) = N. Bạn sẽ giúp anh Kiên chứ?

Input

• Gồm không quá 5 dòng, mỗi dòng chứa một bộ dữ diệu bao gồm 2 số nguyên dương B và N (~ 2 < B ≤ 10000, 0 < N < 2^{63}~).

Output

• Đưa ra kết quả trên nhiều dòng ứng với các bộ dữ liệu ở đầu vào, mỗi dòng đưa ra số nguyên dương X duy nhất là kết quả bài toán. Nếu không tồn tại X hoặc X ≥ ~ 2^{63}~, in ra NOSOLUTION.

Sample

Input #1

10 24
3679 8414548298956800000

Output #1

38
NO SOLUTION

Input #2

12 13
4 12

Output #2

NO SOLUTION
43

Problem source: Free Contest thi thử HSG QG V2