题目描述

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

输入格式

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

输出格式

For each test case, output a single integer denoting the number of unique values $f(\text{lo}, \text{hi})$ can have for the input sequence. Do not output any spaces, and do not print any blank lines between answers.

2
4
6
3
3
6
8
0

3
5