说明

饥饿的鼹鼠在路上发现了一群蚂蚁$s$， 这群蚂蚁是由 n 只蚂蚁排成一排组成的，编号为 1到 n，每只蚂蚁有一个战斗值 $s_{i}$。

为了让自己吃的有趣，鼹鼠想起了一部电影《饥饿游戏》。他每次会随机选择一个区间[L,R]，让这个区间内的蚂蚁两两进行战斗，如果战斗值 $s_{i}$ 能整除 $s_{j}$（即 $s_{i}$ 是 $s_{j}$ 的约数）， $i$号蚂蚁将赢得胜利，并得到一分。如果得分为满分（即 $s_{i}$是这个区间所有战斗值的约数），鼹鼠将释放这只蚂蚁，其他的蚂蚁将被留下来。 每次选择一个新的区间时，区间内的所有蚂蚁初始得分都为 0。

鼹鼠想知道每次战斗后这个区间内还有多少只蚂蚁没有被释放（将被自己吃掉。哈哈哈，好吃！）

输入格式

第一行一个整数$n$，表示$n$ 只蚂蚁。

第二行 $n$个整数，表示每只蚂蚁的战斗值 $s_{i}$。

第三行一个整数 $t$，表示区间数量。

最后$t$行，每行两个整数 $l_{i}$,$r_{i}$，表示区间范围。

输出格式

输出 $t$行，每行输出这个区间中还有多少只蚂蚁没有被释放。

样例

5
1 3 2 4 2
4
1 5
2 5
3 5
4 5

4
4
1
1

样例解释

样例 1：

在区间[1,5]中， 战斗过后 v=[4,0,2,0,2]， 1 号蚂蚁满分，被释放，区间内还留下4只蚂蚁；

在区间[2,5]中，战斗过后 v=[0,2,0,2]，没有蚂蚁得满分，区间内还留下 4 只蚂蚁；

在区间[3,5]中， 战斗过后 v=[2,0,2]， 3 号和 5 号蚂蚁满分，被释放，区间内还留下1只 蚂蚁；

在区间[4,5]中，战斗过后 v=[0,1]， 5 号蚂蚁满分，被释放，区间内还留下 1 只蚂蚁；

数据范围

对于 30%的数据， $1\leqslant n \leqslant 100,1\leqslant t\leqslant 100,1\leqslant s_{i} \leqslant 10^{4},1\leqslant l_{i}\leqslant r_{i}\leqslant n$

对于 100%的数据， $1\leqslant n \leqslant 10^{5},1\leqslant t\leqslant 10^{5},1\leqslant s_{i} \leqslant 10^{9},1\leqslant l_{i}\leqslant r_{i}\leqslant n$

来源

Codeforces 474F