Một số nguyên dương M được gọi là một số đặc biệt nếu nó thỏa mãn: Tổng các chữ số của M bằng tổng các chữ số của các thừa số nguyên tố là tích của M. Chẳng hạn như số 4937775 là một số đặc biệt vì:
4937775 = 3 . 5 . 5 . 65837
Ta có: 4 + 9 + 3 + 7 + 7 + 7 + 5 = 42
Và: 3 + 5 + 5 + 6 + 5 + 8 + 3 + 7 = 42
Yêu cầu: Cho trước một số nguyên dương N. Tìm số đặc biệt nhỏ nhất lớn hơn N.
Dữ liệu vào:
Gồm duy nhất 1 dòng là 1 số nguyên dương N (N< 109)
Kết quả:
Gồm duy nhất 1 dòng là 1 số đặc biệt nhỏ nhất lớn hơn N
Input
4937770
Output
4937775
Nguồn: DHBB'15 H.Nam