//#pragma comment(linker, "/STACK:102400000, 102400000")

 #include <algorithm>

 #include <iostream>

 #include <cstdlib>

 #include <cstring>

 #include <cstdio>

 #include <vector>

 #include <cmath>

 #include <ctime>

 #include <list>

 #include <set>

 #include <map>

 using namespace std;

 typedef long long LL;

 typedef pair <int, int> P;

 const int N = 1e6 + ;

 int a[N/ + ], bit[N]; //_pos存的是gcd上一次出现的位置

 vector <P> ans[N/ + ]; //存的是以i为右端点的gcd

 map <int, int> _pos;

 struct query {

     int l, r, pos;

     bool operator <(const query& cmp) const {

         return r < cmp.r;

     }

 }q[N/ + ];

 int res[N/ + ]; //答案

 void init(int n) {

     _pos.clear();

     memset(bit, , sizeof(bit));

     for(int i = ; i <= n; ++i) {

         ans[i].clear();

     }

 }

 int GCD(int a, int b) {

     return b ? GCD(b, a % b): a;

 }

 void add(int i, int x) {

     for( ; i <= N; i += (i&-i))

         bit[i] += x;

 }

 int sum(int i) {

     int s = ;

     for( ; i >= ; i -= (i&-i))

         s += bit[i];

     return s;

 }

 int main()

 {

     int n, m, t;

     scanf("%d", &t);

     while(t--) {

         scanf("%d %d", &n, &m);

         init(n);

         for(int i = ; i <= n; ++i) {

             scanf("%d", a + i);

         }

         for(int i = ; i <= m; ++i) {

             scanf("%d %d", &q[i].l, &q[i].r);

             q[i].pos = i;

         }

         for(int i = ; i <= n; ++i) {

             int x = a[i], y = i;

             for(int j = ; j < ans[i - ].size(); ++j) {

                 int gcd = GCD(x, ans[i - ][j].first);

                 if(gcd != x) {

                     ans[i].push_back(make_pair(x, y));

                     x = gcd, y = ans[i - ][j].second;

                 }

             }

             ans[i].push_back(make_pair(x, y));

         }

         sort(q + , q + m + );

         int p = ;

         for(int i = ; i <= n; ++i) {

             for(int j = ; j < ans[i].size(); ++j) {

                 if(!_pos[ans[i][j].first]) {

                     add(ans[i][j].second, );

                     _pos[ans[i][j].first] = ans[i][j].second;

                 } else {

                     add(_pos[ans[i][j].first], -);

                     _pos[ans[i][j].first] = ans[i][j].second;

                     add(ans[i][j].second, );

                 }

             }

             while(i == q[p].r && p <= m) {

                 res[q[p].pos] = sum(q[p].r) - sum(q[p].l - );

                 ++p;

             }

         }

         for(int i = ; i <= m; ++i) {

             printf("%d\n", res[i]);

         }

     }

     return ;

 }