题目描述

给定一个包含 $n$ 个数的序列 $\mathbf{A}$，定义 $f(\text{lo}, \text{hi})$（$1 \leq \text{lo} \leq \text{hi} \leq n$）为从 $\mathbf{A}_{\text{lo}}$ 到 $\mathbf{A}_{\text{hi}}$（包含两端）所有数的最大公约数。注意，$\text{lo}$ 和 $\text{hi}$ 是下标，而不是列表中的元素。给定一个数组，考虑所有可能的 $\text{lo}$ 和 $\text{hi}$ 取值，$f(\text{lo}, \text{hi})$ 会有多少个不同的值？

输入格式

输入中有多个测试用例。每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 100{,}000$），表示序列的长度。接下来的 $n$ 行，每行包含一个整数 $a$（$1 \leq a \leq 100$）。这些是按顺序给出的序列中的数。输入以一行一个 0 结束。测试数据大小约 10 MB。

输出格式

对于每个测试用例，输出一个整数，表示输入序列中 $f(\text{lo}, \text{hi})$ 可能取到的不同值的个数。不要输出任何空格，也不要在答案之间打印空行。

2
4
6
3
3
6
8
0

3
5

提示

翻译由 DeepSeek V3.2 完成