OpenKattis
Kattis Set 08

#### Start

2020-03-09 05:15 AKDT

## Kattis Set 08

#### End

2020-03-16 01:30 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -263 days 13:01:59

164:15:00

0:00:00

# Problem KGCDs

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