给定一个长度为 N 的序列 A, 有 Q 次询问。
每次询问给定一个区间 [l,r] ，记 m 为 A_l,A_{l+1},A_{l+2},...,A_r 中的最大值，请统计 A_l,A_{l+1},A_{l+2},...,A_r 中有多少数和 m 互质。
注：如果 a,b 互质，则 a,b 的最大公约数为 1。
第一行两个正整数 N,Q。
第二行 N 个正整数，表示序列 A。
接下来 Q 行，每行两个正整数 l,r 表示一个询问。
输出Q行，每行一个非负整数，一次回答每个询问。
输入样例1：
6 3 1 2 3 4 2 4 1 4 1 3 4 6
输出样例1：
2 2 0
样例解释
区间[1,4]的最大值为4，该区间内有2个数与4互质。分别为：1,3。
区间[1,3]的最大值为3，该区间内有2个数与3互质。分别为：1,3。
区间[4,6]的最大值为4，该区间内没有数与4互质。
对于20%的数据，有 1<=N,Q<=10^3 。
对于另外20%的数据，有 1<=A_i<=2 。
对于所有数据，有 1<=N,Q<=10^5, 1<=A_i<=20, 1<=l<=r<=N 。