时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
小乐乐上了一节数学课，数学老师讲的很好，小乐乐听的也如痴如醉。
小乐乐听了老师的讲解，知道了什么是素数，现在他想做几个习题。
现在题目来了：
首先我们先定义孤独的数：在一个区间中的一个数字x,如果他与这个区间中的任何数都互质，那么他就是孤独的数。
我们给定一个序列，然后接下来会有多次询问，对于每次询问，给定两个整数l, r,我想知道对于(a[l], a[l + 1], ...., a[r])区间来说中有多少孤独的数。
输入描述:
多组样例输入。
对于每一组来说，给定两个整数n和m(1 <= n, m <= 100000),代表序列的长度和询问的次数,
接下来一行有一个长度为n的整数数组a，对于第i个整数a[i], (1 <= a[i] <= 100000)。
接下开m行，每行两个整数l, r(1 <= l <= r <= n),代表区间的左端点位置和有端点位置。
输出描述:
对于每个询问，输出一行，只有一个整数，代表询问的区间中，孤独的数的数量为多少。
示例1
说明
对于第一次询问来说，1, 3, 5是孤独的数。
对于第二次询问来说，3，4是孤独的数。