Vào thế kỷ trước một nhà toán học đã định nghĩa hàm \(f\) trên dãy gồm \(N\) số nguyên dương \(A = a_{1}, a_{2}, ..., a_{n}\) như sau: \(f(i,j) = gcd(a_{i}, a_{i + 1}, ..., a_{j - 1}, a_j)\) với \(1 ≤ i ≤ j ≤ N\), trong đó \(gcd(a_{i}, a_{i + 1}, ..., a_{j - 1}, a_j)\) là ước chung lớn nhất của các số \(a_{i}, a_{i + 1}, ..., a_{j - 1}, a_j\).

Vài năm sau đó một nhà toán học khác áp dụng hàm \(f\) trên dãy \(1, 1, ..., 1\) và nhận xét rằng hàm \(f\) luôn có giá trị bằng \(1\). Trên cơ sở đó ông ta đưa ra giả thiết là giá trị của hàm \(f\) luôn là một hằng số mà không phụ thuộc gì vào dãy \(𝐴\).

Yêu cầu:

Với kiến thức toán học và lập trình của mình bạn hãy bác bỏ giả thiết trên bằng cách chỉ ra hàm \(f\) có thể có nhiều giá trị khác nhau trên dãy \(A\) cho trước.

Dữ liệu vào:

• Dòng 1 ghi số nguyên dương \(N\).
• Dòng 2 ghi \(N\) số nguyên dương \(a_{1}, a_{2}, ..., a_{N}\) \((1 ≤ a_{i} ≤ 10^{18})\)

Kết quả:

Gồm một dòng ghi một số là số giá trị khác nhau của hàm \(f\) trên dãy \(A\) đã cho.

Ví dụ

Sample Input 1:

4
9 6 2 4

Sample Output 1:

6

Sample Input 2:

4
9 6 3 4

Sample Output 2:

5

Ràng buộc:

• Có \(40\%\) số lượng test thoả mãn \(N ≤ 1000\)
• Có \(30\%\) số lượng test thoả mãn \(N ≤ 5000\)
• Có \(30\%\) số lượng test thoả mãn \(N ≤ 100000\).