Given an array ~A~ of length ~N~, count the number of distinct greatest common divisors (GCDs) of all subarrays of this array.

We define the greatest common divisor of a subarray as the greatest common divisor of all the subarray's elements.

Input Specification

The first line of input will contain the integer ~N\ (1 \leq N \leq 10^5)~, the length of the array ~A~.

The next line will contain ~N~ space separated integers ~A_i\ (1 \leq A_i \leq 10^9)~

Output Specification

One line, the number of distinct subarray GCDs.

Subtasks

Subtask 1 [30%]

~N \leq 10^3~

Subtask 2 [70%]

No further restrictions.

Sample Input

3
1 6 4

Sample Output

4