Cho dãy gồm ~N~ số nguyên dương ~A = a_1, a_2, \ldots, a_N~.

Một nhà toán học định nghĩa hàm ~f~ trên dãy như sau: ~f(i,j) = \gcd(a_i, a_{i+1}, \ldots, a_{j-1}, a_j) \quad \text{với } 1 \le i \le j \le N,~ trong đó ~\gcd(a_i, a_{i+1}, \ldots, a_j)~ là ước chung lớn nhất của các số ~a_i, a_{i+1}, \ldots, 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,\ldots,1~ và nhận xét rằng hàm ~f~ luôn có giá trị bằng ~1~. Từ đó ông đưa ra giả thiết rằng giá trị của hàm ~f~ luôn là một hằng số và không phụ thuộc gì vào dãy ~A~.

Yêu cầu: Với kiến thức toán học và lập trình của mình, hãy bác bỏ giả thiết trên bằng cách chỉ ra rằng hàm ~f~ có thể có nhiều giá trị khác nhau trên dãy ~A~ cho trước. Cụ thể, hãy tính số lượng giá trị phân biệt của ~f(i,j)~ khi ~1 \le i \le j \le N~.

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, \ldots, a_N~ ~(1 \le a_i \le 10^{18})~.

Kết quả:

• Một dòng ghi một số là số lượng giá trị khác nhau của ~f~ trên dãy ~A~ đã cho.

Input

Output

Sample Input 1

4
9 6 2 4

Sample Output 1

6

Sample Input 2

4
9 6 3 4

Sample Output 2

5