Kristen yêu thích trò chơi so sánh các con số. Cô ấy định nghĩa rằng với hai số nguyên dương nếu số nào có tổng các chữ số lớn hơn thì số đó tốt hơn, nếu hai số có tổng các chữ số bằng nhau thì số nhỏ hơn sẽ tốt hơn.

Yêu cầu: Cho số nguyên dương ~ n ~ hãy tìm ước số tốt nhất của ~ n ~.

Ví dụ với ~ n = 12 ~ thì ~ n ~ có các ước số ~ {1, 2, 3, 4, 6, 12} ~ trong đó ước số tốt nhất là ~ 6 ~ vì ~ 6 ~ có tổng các chữ số lớn nhất.

Dữ liệu vào

• Số nguyên dương ~ n ~ ~ (n ≤ 10^5 ) ~

Kết quả

• Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ:

Input 1

12 

Output 1

6