Problem K
GCDs

Given a sequence $A$ of $n$ numbers, define $f(lo,hi)$, $1 \le lo \le hi \le n$, as the Greatest Common Divisor of all the numbers $A_{lo}$ through $A_{hi}$, inclusive. Note that $lo$ and $hi$ are indices, not members of the list. Given an array, considering all possible values of $lo$ and $hi$, how many unique values of $f(lo,hi)$ will there be?

Input

There will be a single test case in the input. This test case will begin with a line with a single integer $n$ ($1 \le n \le 100\, 000$) representing the length of the sequence. The next $n$ lines will each have an integer $a$ ($1 \le a \le 100$). These are the numbers in the sequence, in sequence order.

Output

Output a single integer denoting the number of unique values $f(lo,hi)$ can have for the input sequence.

2
4
6

3

3
3
6
8

5