1
#include<bits/stdc++.h>
2
 
3
typedef long long ll;
4
typedef std::pair<int, int> pii;
5
 
6
#define fi first
7
#define se second
8
#define pp push_back
9
#define inarr(n, arr) for(int ax = 0; ax<(n); ax++)cin>>(arr)[ax];
10
#define all(x) (x).begin(), (x).end()
11
#define allr(x) x.rbegin(),(x).rend()
12
#define Ones(n) __builtin_popcount(n)
13
#define endl '\n'
14
#define PI acos(-1)
15
#define sin(a) sin((a)*PI/180)
16
#define cos(a) cos((a)*PI/180)
17
#define tan(a) tan((a)*PI/180)
18
#define yes cout<<"YES\n";
19
#define no cout<<"NO\n";
20
//#define int long long
21
using namespace std;
22
 
23
void Gamal() {
24
    ios_base::sync_with_stdio(false);
25
    cin.tie(nullptr);
26
    cout.tie(nullptr);
27
#ifndef ONLINE_JUDGE
28
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
29
#endif
30
}
31
 
32
int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
33
int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};
34
 
35
const double EPS = 1e-9;
36
const ll N = 1e6 + 5, INF = INT_MAX, MOD = 1e9 + 7;
37
 
38
int spf[N],frq[N],grp[N],mx,arr[N];
39
vector<int> fac[N];
40
 
41
void build() {
42
    for (int i = 1; i < N; ++i) {
43
        spf[i] = i;
44
    }
45
    for (int i = 2; i < N; ++i) {
46
        if (spf[i] != i)continue;
47
        for (int j = 2 * i; j < N; j += i) {
48
            if (spf[j] == j)
49
                spf[j] = i;
50
        }
51
    }
52
    for (int i = 2; i < N; ++i) {
53
        int tmp = i;
54
        while (tmp > 1) {
55
            int x = spf[tmp];
56
            fac[i].pp(x);
57
            while (tmp % x == 0){
58
                tmp /= x;
59
            }
60
        }
61
    }
62
}
63
 
64
int block_size;
65
 
66
bool cmp(pair<pair<int, int>,int> &p, pair<pair<int, int>,int> &q) {
67
    if (p.fi.fi / block_size != q.fi.fi / block_size)
68
        return p.fi.fi < q.fi.fi;
69
    return (p.fi.fi/block_size & 1) ? (p.fi.se < q.fi.se) : (p.fi.se> q.fi.se);
70
}
71
 
72
 
73
void add(int i){
74
    i = arr[i];
75
    for(auto x:fac[i]){
76
        grp[frq[x]]--;
77
        frq[x]++;
78
        grp[frq[x]]++;
79
        mx = max(mx,frq[x]);
80
    }
81
}
82
 
83
void del(int i){
84
    i = arr[i];
85
    for(auto x:fac[i]){
86
        grp[frq[x]]--;
87
        if(mx == frq[x] && !grp[frq[x]]){
88
            mx--;
89
        }
90
        frq[x]--;
91
        grp[frq[x]]++;
92
    }
93
}
94
 
95
 
96
void solve() {
97
    int n, q;
98
    cin >> n >> q;
99
    block_size = (int) sqrt(n + .0) + 1;
100
    for (int i = 0; i < n; ++i) {
101
        cin >> arr[i];
102
    }
103
    vector<pair<pii, int>> queries(q);
104
    vector<int> ans(q);
105
    for (int i = 0; i < q; ++i) {
106
        cin >> queries[i].fi.fi >> queries[i].fi.se;
107
        queries[i].fi.fi--, queries[i].fi.se--;
108
        queries[i].se = i;
109
    }
110
    sort(all(queries), cmp);
111
    int l = 1;
112
    int r = 0;
113
    for (auto query: queries) {
114
        while (l > query.fi.fi)add(--l);
115
        while (r < query.fi.se)add(++r);
116
        while (l < query.fi.fi)del(l++);
117
        while (r > query.fi.se)del(r--);
118
        ans[query.se] = mx;
119
    }
120
    for (int i = 0; i < q; ++i) {
121
        cout<<ans[i]<<endl;
122
    }
123
    while (l <= r)del(l++);
124
}
125
 
126
 
127
signed main() {
128
    Gamal();
129
    build();
130
    int t = 1;
131
    cin >> t;
132
    while (t--) {
133
        solve();
134
    }
135
}