ssdasdasd

//Слава Україні, Героям слава

#include <bits/stdc++.h>

using namespace std;

int sqt;

struct fuck {
    int l, r, t;
    friend bool operator < (const fuck a, const fuck b) {
        if(a.l / sqt == b.l / sqt) {
            return a.r < b.r;
        } else {
            return a.l / sqt < b.l / sqt;
        }
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> v(n), ans(q), pr(n, -1);
    vector<fuck> qq(q);
    sqt = sqrtl(n);
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        map<int, int> mp;
        int x = v[i];
        for(long long j = 2; j * j <= x; j++) {
            while(x % j == 0) {
                x /= j;
                mp[j]++;
            }
        }
        if(x != 1) mp[x]++;
        if(mp.size() == 1) {
            pr[i] = mp.begin()->first;
        } else if(mp.size() == 0) {
            pr[i] = 4;
        }
    }
    for(int i = 0; i < q; i++) {
        cin >> qq[i].l >> qq[i].r;
        qq[i].l--;
        qq[i].r--;
        qq[i].t = i;
    }
    sort(qq.begin(), qq.end());
    int l = 0, r = -1;
    int cnt = 0, oth = 0;
    map<int, int> mp;
    multiset<int> ms;
    ms.insert(0);
    for(int i = 0; i < q; i++) {
        while(l > qq[i].l) {
            l--;
            if(pr[l] == -1) {
                cnt++;
            } else {
                if(mp[pr[l]] != 0) {
                    ms.erase(ms.find(mp[pr[l]]));
                }
                mp[pr[l]]++;
                oth++;
                ms.insert(mp[pr[l]]);
            }
        }
        while(r > qq[i].r) {
            if(pr[r] == -1) {
                cnt--;
            } else {
                ms.erase(ms.find(mp[pr[r]]));
                mp[pr[r]]--;
                oth--;
                if(mp[pr[r]] == 0) {
                    mp.erase(pr[r]);
                } else {
                    ms.insert(mp[pr[r]]);
                }
            }
            r--;
        }
        while(l < qq[i].l) {
            if(pr[l] == -1) {
                cnt--;
            } else {
                ms.erase(ms.find(mp[pr[l]]));
                mp[pr[l]]--;
                oth--;
                if(mp[pr[l]] == 0) {
                    mp.erase(pr[l]);
                } else {
                    ms.insert(mp[pr[l]]);
                }
            }
            l++;
        }
        while(r < qq[i].r) {
            r++;
            if(pr[r] == -1) {
                cnt++;
            } else {
                if(mp[pr[r]] != 0) {
                    ms.erase(ms.find(mp[pr[r]]));
                }
                mp[pr[r]]++;
                oth++;
                ms.insert(mp[pr[r]]);
            }
        }
        if(!cnt and (mp.size() == 1 or (mp.size() == 2 and mp.find(4) != mp.end()))) {
            ans[qq[i].t] = -1;
        } else {
            int mx = *ms.rbegin();
            if(mx * 2 > oth) {
                ans[qq[i].t] = mx;
                if(mp.find(4) != mp.end()) {
                    if(mx == mp[4]) {
                        auto itr = ms.end();
                        itr--; itr--;
                        int nmx = *itr;
                        if(nmx * 2 > oth - mp[4]) {
                            ans[qq[i].t] = nmx + mp[4];
                        } else {
                            ans[qq[i].t] = (oth - mp[4] + 1) / 2 + mp[4];
                        }
                    } else {
                        ans[qq[i].t] = mx + mp[4];
                    }
                }
            } else {
                ans[qq[i].t] = (oth + 1) / 2;
                if(mp.find(4) != mp.end()) {
                    if(mx * 2 > oth - mp[4] and mx != mp[4]) {
                        ans[qq[i].t] = mx + mp[4];
                    } else {
                        if(mx * 2 == oth and mp.size() == 2) {
                            ans[qq[i].t] = oth;
                        } else {
                            auto itr = ms.end();
                            itr--; itr--;
                            int nmx = *itr;
                            if(nmx * 2 > oth - mp[4]) {
                                ans[qq[i].t] = nmx + mp[4];
                            } else {
                                ans[qq[i].t] = (oth - mp[4] + 1) / 2 + mp[4];
                            }
                        }
                    }
                }
            }
        }
    }
    for(auto e : ans) {
        cout << e << "\n";
    }
    return 0;
}