Hiện nay, xem ý nghĩa biển số xe, số điện thoại, ngày sinh hay một dãy số nào đó là điều quan tâm của nhiều người. Cách đánh giá số đẹp của dãy số như sau: Tính tổng các chữ số trong dãy, nếu tổng là số có 1 chữ thì đó là giá trị số đẹp(độ đẹp của dãy số), ngược lại thì tiếp tục tính tổng các chữ số trong dãy.

Ví dụ: Dãy số ngày sinh 02022020 có tổng các chữ số là 8, vậy độ đẹp của dãy số là 8. Dãy số điện thoại 0912345678 có tổng các chữ số là 45, tính tục tính tổng ta được tổng là 9, vậy độ đẹp của dãy số là 9.

Yêu cầu: Cho dãy số có n chữ số. Hãy đánh giá độ đẹp của dãy số đã cho.

Input

• Chứa dãy số có n chữ số (n≤18)

Output

• Một số nguyên là độ đẹp của dãy số.

Example

Test 1

Input

02022020

Output

8

Test 2

Input

0912345678

Output

9

Ước số chung của dãy số nguyên dương là các số nguyên dương mà tất cả các số trong dãy đều chia hết cho nó. Hôm nay, Tuấn đang học về ước số chung và Tuấn được thầy giáo cho bài toán: Có một dãy số ~A~ gồm ~N~ số nguyên dương, hãy tìm ước số chung nhỏ nhất khác 1. Nói cách khác, Tuấn cần tìm số D nhỏ nhất, sao cho ~D >1~ và các số trong dãy số ~A~ đều chia hết cho số ~D~ này.

Yêu cầu: Cho một số ~A~ gồm ~N~ số nguyên dương, hãy giúp Tuấn đưa ra số là Ước số chung nhỏ nhất khác 1.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N≤10^5~)
• Dòng tiếp theo gồm ~N~ số nguyên dương ~A_i~​ là các phần tử của dãy ~A~ (~A_i≤10^6~).

Output

• Một số nguyên dương ước chung nhỏ nhất của dãy số. Nếu không tồn tại số nào, in ra -1.

Scoring

• Subtask 1 (60% số điểm): N≤10^3, ~A_i≤10^5~.

• Subtask 2 (40% số điểm): Không có ràng buộc gì thêm

Example

Test 1

Input

3
1 2 3

Output

-1

Test 2

Input

3
2 4 6

Output

2