// PRAGMAS
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

// INCLUDES
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace std;

// DEFINES
#define int               long long
#define mp                make_pair
#define pb                push_back
#define eb                emplace_back
#define ins               insert
#define all(x)            (x).begin(),(x).end()
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define inparr(x,n)       for(int _i = 0; _i < (n); ++_i)cin>>(x)[_i];
#define popcnt            __builtin_popcountll
#define elasped_time      1.0 * clock() / CLOCKS_PER_SEC 

// TYPEDEFS
using ll = long long;
using str = string;
using pii = pair<int,int>;
using vi = vector<int>;
using vii = vector<pii>;
using vvi = vector<vi>;
template<class T> using vec = vector<T>;

// I/O
void setPrec(int prec) { cout << fixed << setprecision(prec); }
void unsyncIO() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }

// INPUT
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.fr<<" "<<a.sc;return out;}

template<class T, class U> void read(pair<T,U>& p);
template<class T> void read(vector<T>& v);

template<class T> void read(T& x) { cin >> x; }
void read(double& d) { str t; read(t); d = stod(t); }
void read(long double& d) { str t; read(t); d = stold(t); }
template<class T, class ...U> void read(T& t, U&... u) { read(t); read(u...); }
template<class T, class U> void read(pair<T,U>& p) { read(p.fr,p.sc); }
template<class T> void read(vector<T>& x) { for(auto &z: x) read(z); }
template<class T> void readn(vector<T>& x, int n) { x.resize(n); for(auto &z: x) read(z); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
    #ifdef LOCAL
        return b ? "true" : "false"; 
    #else 
        return ts((int)b);
    #endif
}

template<size_t SZ> str ts(bitset<SZ> b) { str res = ""; for(int i = 0; i < SZ; ++i) res += char('0'+b[i]); return res; }
template<class T, class U> str ts(pair<T,U> p);
template<class T> str ts(T v) { // containers with begin(), end()
    #ifdef LOCAL
        bool fst = 1; str res = "{";
        for (const auto& x: v) {
            if (!fst) res += ", ";
            fst = 0; res += ts(x);
        }
        res += "}"; return res;
    #else
        bool fst = 1; str res = "";
        for (const auto& x: v) {
            if (!fst) res += " ";
            fst = 0; res += ts(x);
        }
        return res;
    #endif
}

template<class T, class U> str ts(pair<T,U> p) {
    #ifdef LOCAL
        return "("+ts(p.fr)+", "+ts(p.sc)+")"; 
    #else
        return ts(p.fr)+" "+ts(p.sc);
    #endif
}
 
// OUTPUT
template<class T> void pr(T x) { cout << ts(x); }
template<class T, class ...U> void pr(const T& t, const U&... u) { pr(t); pr(u...); }
void write() { pr("\n"); } // print w/ spaces
template<class T, class ...U> void write(const T& t, const U&... u) { 
    pr(t); if (sizeof...(u)) pr(" "); write(u...); }
 
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class T,class ...U> void DBG(const T& t, const U&... u) {
    cerr << ts(t); if (sizeof...(u)) cerr << ", ";
    DBG(u...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
    #define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
    #define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
         << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
    #define dbg(...) 0
    #define chk(...) 0
#endif

// MISC
template<class T> int lwb(vector<T>& a, const T& b) { return lower_bound(all(a),b)-(a).begin(); }
template<class T> void uniq(vector<T>& v) { sort(all(v)); v.erase(unique(all(v)),v.end()); }

// template<typename T>
// using oset = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;

template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const long long inf = 1e18;
const int hell = 1e9+7; // 998244353;
const long double PI = acos((long double)-1);
const int maxn = 100005;

int lp[maxn + 1];
vector<int> primes;
void sieve(){
    static bool built=0;
    if (built) return;
    built = 1;
    for (int i = 2; i<=maxn; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            primes.push_back(i);
        }
        for (int j = 0; j < (int)primes.size() && primes[j] <= lp[i] && i * primes[j] <= maxn; ++j){
            lp[i * primes[j]] = primes[j];
        }
    }
}
vi lst(maxn, -1);
void solve(){
    sieve();
    int n, q;
    read(n, q);
    vi a(n);
    read(a);
    vi nxt(n + 1, n);
    for (int i = 0; i < n; ++i) {
        int t = a[i];
        while (t > 1) {
            int p = lp[t];
            while (t % p == 0) t /= p;
            if (lst[p] != -1) amin(nxt[lst[p]], i);
            lst[p] = i;
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        nxt[i] = min(nxt[i], nxt[i + 1]);
    }
    vvi par(17, vi(n + 1));
    for (int i = 0; i <= n; ++i) {
        par[0][i] = nxt[i];
    }
    for (int i = 1; i < 17; ++i) {
        for (int j = 0; j <= n; ++j) {
            par[i][j] = par[i - 1][par[i - 1][j]];
        }
    }
    for (int ii = 0; ii < q; ++ii) {
        int l, r;
        read(l, r);
        l--, r--;
        int ans = 1;
        for (int i = 16; i >= 0; --i) {
            if (par[i][l] <= r) {
                ans += (1<<i);
                l = par[i][l];
            }
        }
        assert (nxt[l] > r);
        write(ans);
    }
    
}

signed main(){
    unsyncIO();
    // setPrec(9);
    // setIn("input.txt");
    // setOut("output.txt");
    int cases=1;
    // cin>>cases;
    for (int i = 1; i <= cases; ++i) {
        solve();
    }
    #ifdef LOCAL
        cerr<<endl<<"Time Elasped : "<<elasped_time<<endl;
    #endif
    return 0;
}

### Prompt

Generate a CPP solution to the following problem:

This time Baby Ehab will only cut and not stick. He starts with a piece of paper with an array a of length n written on it, and then he does the following:

  * he picks a range (l, r) and cuts the subsegment a_l, a_{l + 1}, …, a_r out, removing the rest of the array. 
  * he then cuts this range into multiple subranges. 
  * to add a number theory spice to it, he requires that the elements of every subrange must have their product equal to their [least common multiple (LCM)](https://en.wikipedia.org/wiki/Least_common_multiple). 



Formally, he partitions the elements of a_l, a_{l + 1}, …, a_r into contiguous subarrays such that the product of every subarray is equal to its LCM. Now, for q independent ranges (l, r), tell Baby Ehab the minimum number of subarrays he needs.

Input

The first line contains 2 integers n and q (1 ≤ n,q ≤ 10^5) — the length of the array a and the number of queries.

The next line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^5) — the elements of the array a.

Each of the next q lines contains 2 integers l and r (1 ≤ l ≤ r ≤ n) — the endpoints of this query's interval.

Output

For each query, print its answer on a new line.

Example

Input


6 3
2 3 10 7 5 14
1 6
2 4
3 5


Output


3
1
2

Note

The first query asks about the whole array. You can partition it into [2], [3,10,7], and [5,14]. The first subrange has product and LCM equal to 2. The second has product and LCM equal to 210. And the third has product and LCM equal to 70. Another possible partitioning is [2,3], [10,7], and [5,14].

The second query asks about the range (2,4). Its product is equal to its LCM, so you don't need to partition it further.

The last query asks about the range (3,5). You can partition it into [10,7] and [5].

### Response

```cpp
// PRAGMAS
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
// #pragma GCC optimize("unroll-loops")

// INCLUDES
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace std;

// DEFINES
#define int               long long
#define mp                make_pair
#define pb                push_back
#define eb                emplace_back
#define ins               insert
#define all(x)            (x).begin(),(x).end()
#define sz(x)             (int)((x).size())
#define fr                first
#define sc                second
#define inparr(x,n)       for(int _i = 0; _i < (n); ++_i)cin>>(x)[_i];
#define popcnt            __builtin_popcountll
#define elasped_time      1.0 * clock() / CLOCKS_PER_SEC 

// TYPEDEFS
using ll = long long;
using str = string;
using pii = pair<int,int>;
using vi = vector<int>;
using vii = vector<pii>;
using vvi = vector<vi>;
template<class T> using vec = vector<T>;

// I/O
void setPrec(int prec) { cout << fixed << setprecision(prec); }
void unsyncIO() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); }
void setIn(str s) { freopen(s.c_str(),"r",stdin); }
void setOut(str s) { freopen(s.c_str(),"w",stdout); }

// INPUT
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.fr>>a.sc;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.fr<<" "<<a.sc;return out;}

template<class T, class U> void read(pair<T,U>& p);
template<class T> void read(vector<T>& v);

template<class T> void read(T& x) { cin >> x; }
void read(double& d) { str t; read(t); d = stod(t); }
void read(long double& d) { str t; read(t); d = stold(t); }
template<class T, class ...U> void read(T& t, U&... u) { read(t); read(u...); }
template<class T, class U> void read(pair<T,U>& p) { read(p.fr,p.sc); }
template<class T> void read(vector<T>& x) { for(auto &z: x) read(z); }
template<class T> void readn(vector<T>& x, int n) { x.resize(n); for(auto &z: x) read(z); }

// TO_STRING
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
str ts(bool b) { 
    #ifdef LOCAL
        return b ? "true" : "false"; 
    #else 
        return ts((int)b);
    #endif
}

template<size_t SZ> str ts(bitset<SZ> b) { str res = ""; for(int i = 0; i < SZ; ++i) res += char('0'+b[i]); return res; }
template<class T, class U> str ts(pair<T,U> p);
template<class T> str ts(T v) { // containers with begin(), end()
    #ifdef LOCAL
        bool fst = 1; str res = "{";
        for (const auto& x: v) {
            if (!fst) res += ", ";
            fst = 0; res += ts(x);
        }
        res += "}"; return res;
    #else
        bool fst = 1; str res = "";
        for (const auto& x: v) {
            if (!fst) res += " ";
            fst = 0; res += ts(x);
        }
        return res;
    #endif
}

template<class T, class U> str ts(pair<T,U> p) {
    #ifdef LOCAL
        return "("+ts(p.fr)+", "+ts(p.sc)+")"; 
    #else
        return ts(p.fr)+" "+ts(p.sc);
    #endif
}
 
// OUTPUT
template<class T> void pr(T x) { cout << ts(x); }
template<class T, class ...U> void pr(const T& t, const U&... u) { pr(t); pr(u...); }
void write() { pr("\n"); } // print w/ spaces
template<class T, class ...U> void write(const T& t, const U&... u) { 
    pr(t); if (sizeof...(u)) pr(" "); write(u...); }
 
// DEBUG
void DBG() { cerr << "]" << endl; }
template<class T,class ...U> void DBG(const T& t, const U&... u) {
    cerr << ts(t); if (sizeof...(u)) cerr << ", ";
    DBG(u...); }
#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
    #define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
    #define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
         << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#else
    #define dbg(...) 0
    #define chk(...) 0
#endif

// MISC
template<class T> int lwb(vector<T>& a, const T& b) { return lower_bound(all(a),b)-(a).begin(); }
template<class T> void uniq(vector<T>& v) { sort(all(v)); v.erase(unique(all(v)),v.end()); }

// template<typename T>
// using oset = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;

template<typename T,typename T1>T amax(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T amin(T &a,T1 b){if(b<a)a=b;return a;}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const long long inf = 1e18;
const int hell = 1e9+7; // 998244353;
const long double PI = acos((long double)-1);
const int maxn = 100005;

int lp[maxn + 1];
vector<int> primes;
void sieve(){
    static bool built=0;
    if (built) return;
    built = 1;
    for (int i = 2; i<=maxn; ++i) {
        if (lp[i] == 0) {
            lp[i] = i;
            primes.push_back(i);
        }
        for (int j = 0; j < (int)primes.size() && primes[j] <= lp[i] && i * primes[j] <= maxn; ++j){
            lp[i * primes[j]] = primes[j];
        }
    }
}
vi lst(maxn, -1);
void solve(){
    sieve();
    int n, q;
    read(n, q);
    vi a(n);
    read(a);
    vi nxt(n + 1, n);
    for (int i = 0; i < n; ++i) {
        int t = a[i];
        while (t > 1) {
            int p = lp[t];
            while (t % p == 0) t /= p;
            if (lst[p] != -1) amin(nxt[lst[p]], i);
            lst[p] = i;
        }
    }
    for (int i = n - 1; i >= 0; --i) {
        nxt[i] = min(nxt[i], nxt[i + 1]);
    }
    vvi par(17, vi(n + 1));
    for (int i = 0; i <= n; ++i) {
        par[0][i] = nxt[i];
    }
    for (int i = 1; i < 17; ++i) {
        for (int j = 0; j <= n; ++j) {
            par[i][j] = par[i - 1][par[i - 1][j]];
        }
    }
    for (int ii = 0; ii < q; ++ii) {
        int l, r;
        read(l, r);
        l--, r--;
        int ans = 1;
        for (int i = 16; i >= 0; --i) {
            if (par[i][l] <= r) {
                ans += (1<<i);
                l = par[i][l];
            }
        }
        assert (nxt[l] > r);
        write(ans);
    }
    
}

signed main(){
    unsyncIO();
    // setPrec(9);
    // setIn("input.txt");
    // setOut("output.txt");
    int cases=1;
    // cin>>cases;
    for (int i = 1; i <= cases; ++i) {
        solve();
    }
    #ifdef LOCAL
        cerr<<endl<<"Time Elasped : "<<elasped_time<<endl;
    #endif
    return 0;
}

```