407014 - 区间互质

给定n个数的序列，m个询问，询问区间[L，R]内，有多少个数与区间内其他所有的数都互质。

输入包含多组数据，每组数据第一行为两个整数n和m，接下来一行有n个整数a[i]，随后m行询问，包含两个整数L和R　(1≤n，m，a[i]≤200 000，1≤L≤R≤n)。　 输入结束为两个0。

对于每个询问，输出互质的数的个数。

在第二组测试数据里，询问区间[2，6]的结果是2，因为只有1和5与其他所有数互质。