#### Start

2019-01-27 19:00 CET

## 2019 NAIPC Practice Contest 4

#### End

2019-01-28 00:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -312 days 21:06:24

5:00:00

0:00:00

# Problem EGCDs

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.

Sample Input 1 Sample Output 1
2
4
6

3

Sample Input 2 Sample Output 2
3
3
6
8

5