CF474F.Ant colony

Mole is hungry again. He found one ant colony, consisting of n ants, ordered in a row. Each ant i (1 ≤ i ≤ n) has a strength s__i.

In order to make his dinner more interesting, Mole organizes a version of «Hunger Games» for the ants. He chooses two numbers l and r (1 ≤ l ≤ r ≤ n) and each pair of ants with indices between l and r (inclusively) will fight. When two ants i and j fight, ant i gets one battle point only if s__i divides s__j (also, ant j gets one battle point only if s__j divides s__i).

After all fights have been finished, Mole makes the ranking. An ant i, with v__i battle points obtained, is going to be freed only if v__i = r - l, or in other words only if it took a point in every fight it participated. After that, Mole eats the rest of the ants. Note that there can be many ants freed or even none.

In order to choose the best sequence, Mole gives you t segments [l__i, r__i] and asks for each of them how many ants is he going to eat if those ants fight.

鼹鼠又饿了。他发现了一个由 $n$ 只蚂蚁组成的蚁群，这些蚂蚁排成一列。每只蚂蚁 $i$（$1 \le i \le n$）具有力量值 $s_i$。

为了让晚餐更有趣，鼹鼠为这些蚂蚁组织了一场“饥饿游戏”变体。他选择两个数 $l$ 和 $r$（$1 \le l \le r \le n$），所有下标在区间 $[l, r]$ 内（含端点）的蚂蚁两两之间都将进行一场战斗。当蚂蚁 $i$ 与蚂蚁 $j$ 战斗时，若 $s_i$ 整除 $s_j$，则蚂蚁 $i$ 获得 1 分；同理，若 $s_j$ 整除 $s_i$，则蚂蚁 $j$ 也获得 1 分。

所有战斗结束后，鼹鼠对蚂蚁进行排名。设蚂蚁 $i$ 共获得 $v_i$ 分，则仅当 $v_i = r - l$（即该蚂蚁在其参与的所有战斗中均获得 1 分）时，它才会被释放。随后，鼹鼠吃掉其余所有未被释放的蚂蚁。注意：可能有多个蚂蚁被释放，也可能一个都没有。

为了选出最优的区间，鼹鼠给出 $t$ 个查询区间 $[l_i, r_i]$，并针对每个区间询问：若该区间内的蚂蚁相互战斗，鼹鼠最终将吃掉多少只蚂蚁？

The first line contains one integer n (1 ≤ n ≤ 105), the size of the ant colony.

The second line contains n integers _s_1, _s_2, ..., s__n (1 ≤ s__i ≤ 109), the strengths of the ants.

The third line contains one integer t (1 ≤ t ≤ 105), the number of test cases.

Each of the next t lines contains two integers l__i and r__i (1 ≤ l__i ≤ r__i ≤ n), describing one query.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示蚂蚁群的大小。

第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \leq s_i \leq 10^9$），表示每只蚂蚁的强度。

第三行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。

接下来的 $t$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$），描述一次查询。

Print to the standard output t lines. The i-th line contains number of ants that Mole eats from the segment [l__i, r__i].

向标准输出打印 $t$ 行。第 $i$ 行包含鼹鼠在区间 $[l_i,\,r_i]$ 内吃掉的蚂蚁数量。

In the first test battle points for each ant are v = [4, 0, 2, 0, 2], so ant number 1 is freed. Mole eats the ants 2, 3, 4, 5.

In the second test case battle points are v = [0, 2, 0, 2], so no ant is freed and all of them are eaten by Mole.

In the third test case battle points are v = [2, 0, 2], so ants number 3 and 5 are freed. Mole eats only the ant 4.

In the fourth test case battle points are v = [0, 1], so ant number 5 is freed. Mole eats the ant 4.

第一次测试中，每只蚂蚁的战斗分数为 $v = [4, 0, 2, 0, 2]$，因此编号为 1 的蚂蚁被释放。鼹鼠吃掉了编号为 2、3、4、5 的蚂蚁。

第二次测试中，战斗分数为 $v = [0, 2, 0, 2]$，因此没有蚂蚁被释放，全部被鼹鼠吃掉。

第三次测试中，战斗分数为 $v = [2, 0, 2]$，因此编号为 3 和 5 的蚂蚁被释放。鼹鼠仅吃掉了编号为 4 的蚂蚁。

第四次测试中，战斗分数为 $v = [0, 1]$，因此编号为 5 的蚂蚁被释放。鼹鼠吃掉了编号为 4 的蚂蚁。