Số Smith là một số tự nhiên không phải là số nguyên tố, và tổng các chữ số của nó bằng tổng các chữ số của các thừa số nguyên tố của nó (lấy riêng lẻ từng chữ số của các thừa số). Ví dụ các số Smith đầu tiên \(4, 22, 27, 58, 85, 94, …\)

Ví dụ: \(378 = 2 \times 3 \times 3 \times 3 \times 7\). Tổng các chữ số là \(3 + 7 + 8 = 18.\)

Hãy viết chương trình xác định số Smith lớn hơn \(N\) nhỏ nhất.

INPUT FORMAT

Dòng đầu tiên chứa giá trị \(N (1 \leq N \leq 10^{6})\).

OUTPUT FORMAT

In ra số Smith lớn hơn \(N\) nhỏ nhất.

Ví dụ 1:

Input

377

Ouput

378

Giải thích ví dụ mẫu:

• Ví dụ 1: Số Smith lớn hơn 377 nhỏ nhất là 378, vì 378 là số Smith và lớn hơn 377.

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House