Trong buổi sinh hoặc cắm trại cùng lớp, bạn Cường được tham gia trò chơi truy tìm kho báu do cô chủ nhiệm tổ chức. Có nhiều chiếc hộp khác nhau được cô chủ nhiệm bố trí trong khu vực tìm kho báu, mỗi hộp được đánh một số nguyên dương khác nhau, kho báu được chứa ở một trong các hộp này. Ban đầu cô chủ nhiệm cho lớp một số nguyên dương ~N~, số cần tìm của chiếc hộp kho báu là số nguyên dương ~K~ nhỏ nhất lớn hơn ~N~ thỏa mãn yêu cầu sau: từ số ~K~ ban đầu ta tạo ra số mới bằng cách lấy tổng bình phương các chữ số của nó, với số mới này ta liên tục lặp lại thao tác như trên cho đến khi ta nhận được số mới là ~1~.

Yêu cầu: Hãy giúp bạn Cường tìm được chiếc hộp kho báu theo yêu cầu trên

Dữ liệu vào

Nhập từ bàn phím số nguyên dương ~N~ ~(N\le 10^{16})~

Kết quả ra

Xuất ra màn hình một số nguyên dương ~K~ duy nhất thỏa mãn yêu cầu đề bài.

Ví dụ

Dữ liệu

15

Kết quả

19

Giải thích

~N=15~ ta có số của chiếc hộp là ~19~ thỏa mãn yêu cầu: ~19 \rightarrow 82 \rightarrow 68 \rightarrow 100 \rightarrow 1~ trong đó

• ~82=1^2+9^2~
• ~68=8^2+2^2~
• ~100=6^2+8^2~
• ~1=1^2+0^2+0^2 ~