题目描述

自带社会气息的王老师在路上发现了一群学生，这群学生是由 n 个学生排成一排组成的，编号为 1 到 n，每个学生有一个淘汰值 si。
为了让自己淘汰得有趣，王老师想起了一部电影《淘汰游戏》。他每次会随机选择一个区间 [ L, R ]，让这个区间内的学生两两进行淘汰，如果淘汰值 si 能整除 sj（即 si 是 sj 的约数），i 号学生将赢得胜利，并得到一分。如果得分为满分（即 si 是这个区间所有淘汰值的约数），王老师将释放这个学生，其他的学生将被留下来。每次选择一个新的区间时，区间内的所有学生初始得分都为 0。
王老师想知道每次淘汰后这个区间内还有多少个学生没有被释放。（将被自己淘汰掉。哈哈哈，おもしろい！）

输入描述

第一行一个整数 n，表示 n 个学生。
第二行 n 个整数，表示每个学生的淘汰值 si。
第三行一个整数 t，表示区间数量。
最后 t 行，每行两个整数 li, ri，表示区间范围。

输出描述

输出 t 行，每行输出这个区间中还有多少个学生没有被释放。

样例输入

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

样例输出

4
4
1
1

数据范围

对于 30%的数据，1 <= n <= 100，1 <= t <= 100，1 <= si <= 10000，1 <= li <= ri <= n；
对于 100%的数据，1 <= n <= 10 ^ 5，1 <= t <= 10 ^ 5，1 <= si <= 10 ^ 9，1 <= li <= ri <= n。

限制

1s

样例解释

在区间 [ 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 个学生；

来源

Codeforces474F
CWOI新高二专题测试七