Một dãy số ~(b_1, b_2, ..., b_m)~ được gọi là có thể tối giản nếu tồn tại một phần tử *~x~ thỏa mãn:*

• ~x~ là duy nhất trong dãy.

• Mọi phần tử ~b_1, b_2, ..., b_m~ đều chia hết cho ~x~.

Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~, hãy đếm số cặp chỉ số ~(l, r)~ sao cho dãy ~a_l, a_{l+1}, ..., a_r~ là dãy có thể tối giản. ~(1 \le l < r \le n)~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ ~(1 \le n \le 3 * 10^5)~.

• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(1 \le a_i \le 10^9)~.

Output

• Gồm một dòng duy nhất là số dãy tìm được.

Sample Input 1

5
4 3 6 4 2

Sample Output 1

3

Notes

• Các đoạn thỏa mãn là ~[2, 3], [4, 5], [3, 5]~.