U613849 ggg
题目描述
给一个序列 \(a_i\) ,
\(q\)个询问L R
求从中有多少个区间 \([l,r]\) 满足
$ gcd(a_l,a_{l+1},a_{l+2},·····a_{r})=1 $，
输入格式
第一行一个 \(N\)，满足N为正整数。
第二行序列\(a\)。
第三行 \(q\)
第四行到第3+q行是询问。
输出格式
\(q\)个整数答案。
输入输出样例 #1
输入 #1
5
1 2 3 4 5
3
2 3
2 4
1 1
输出 #1
1
3
1
说明/提示
\(N,q<=10^6\)
\(a_i<=10^9\)
数据保证随机。