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].

Solution (in CPP):

Solution:
﻿#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <math.h> 
#include <iomanip>
#include <fstream>
#include <bitset>
#include <sstream>    
using namespace std;
//#define M_PI (ldb)3.14159265358979323846 // pi 
#define forr(i,a,b,c) for(int i=a;i<b;i+=c)
#define forrb(i,a,b,c) for(int i=a;i>b;i-=c)
#define fori(i,n) forr(i,0,n,1)
#define forit(it,arr) for(auto it=arr.begin();it != arr.end();it++)
#define forib(i,n) forrb(i,n-1,-1,1)
#define forn(i,n) forr(i,1,n,1)
#define fornb(i,n) forrb(i,n-1,0,1)
#define fort(i,m,n) forr(i,m,n,1)
#define fortb(i,m,n) forrb(i,n-1,m-1,1)
#define forin(i,arr) fori(i,arr.size())
#define forinb(i,arr) forib(i,arr.size())
#define forrl(i,a,b,c) for(lol i=a;i<b;i+=c)
#define forrbl(i,a,b,c) for(lol i=a;i>b;i-=c)
#define foril(i,n) forrl(i,0,n,1)
#define foribl(i,n) forrbl(i,n-1,-1,1)
#define fornl(i,n) forrl(i,1,n,1)
#define fornbl(i,n) forrbl(i,n-1,0,1)
#define fortl(i,m,n) forrl(i,m,n,1)
#define fortbl(i,m,n) forrbl(i,n-1,m-1,1)
#define forinl(i,arr) foril(i,arr.size())
#define forinbl(i,arr) foribl(i,arr.size())
#define forpm(i) forr(i,-1,2,2)
#define into(i) cin >> i;
#define intov(arr,n) fori(kkkk,n){into(arr[kkkk])}
#define def(i) lol i; into(i)
#define deft(t,i) t i; into(i)
#define defl(i) lol i; into(i)
#define defs(i) string i; into(i)
#define defn def(n)
#define defp def(p)
#define defm def(m)
#define defk def(k)
#define defa def(a)
#define defb def(b)
#define defc def(c)
#define defd def(d)
//#define vec(a) vector<a>
#define co cout <<
#define out(a) cout << (a) <<' ';
#define el << endl;
#define ell << '\n';
#define outv(arr,n) fori(iii,n){out(arr[iii])} co "" el
#define outvv(arr,n,m) fori(jjj,n){outv(arr[jjj],m)}
#define cas(p) co "Case #" << p+1 <<": ";
#define ex return 0; 
#define qii queue<int>
#define sti stack<int>
#define dei deque<int>
#define seti set<int>
#define con continue;
#define br break;
#define maxi 1000000007
// 998244353
#define maxiu 4294967295
#define lmaxi 2000000000000000007
#define mod %maxi
#define wne(arr) while(!arr.empty())
#define all(arr) arr.begin(),arr.end()
#define getv(arr,n) fori(i,n) {into(arr[i])}
#define defv(arr,n) veci arr(n); fori(i,n) {into(arr[i])}
#define min2(a,b) a=min(a,b);
#define max2(a,b) a=max(a,b);
#define vec vector
#define ff first
#define ss second
#define pow2(x) (x)*(x)
#define pow3(x) (x)*(x)*(x)
#define getgraph(m,cons) fori(i,m){defa defb a--; b--; cons[a].push_back(b);cons[b].push_back(a);}
#define getdirectedgraph(m,cons) fori(i,m){defa defb a--; b--; cons[a].push_back(b);}
#define getwightedgraph(m,cons) fori(i,m){defa defb defc a--; b--; cons[a].push_back({b,c});cons[b].push_back({a,c});}
#define getwighteddirectedgraph(m,cons) fori(i,m){defa defb defc a--; b--; cons[a].push_back({b,c});}
typedef vector<int> veci;
typedef long long lol;
typedef unsigned long long ulol;
typedef unsigned int uint;
typedef long double ldb;
typedef vector<lol> vecl;
typedef vector<uint> vecui;
typedef vector<ulol> vecul;
#define table(name,n,m) vector<veci> name(n,veci (m));
#define tablel(name,n,m) vector<vecl> name(n,vecl (m));
typedef pair<lol, lol> point;
#define setp set<point>
#define bmod %99999999999899999
typedef pair<point, point> poin;
typedef pair<long double, long double> pointd;
typedef pair<lol, point> poing;
typedef pair<point, lol> poinf;
typedef vector<point> vecp;
#define poi(x,y) make_pair(x,y)
struct BigNum {
#define sizer (lol) 1e9
#define digss (lol) 9
	vecl value;
	void set(lol x) { value = *(new vecl); value.push_back(x); }
	void duplicate(BigNum other) { value = other.value; }
	void add(BigNum other) {
		vecl o = other.value;
		if (o.size() > value.size()) {
			vecl t = value;
			value = o;
			o = t;
		}
		forin(i, o) {
			value[i] += o[i];
			if (i < value.size() - 1 && value[i] >= sizer) {
				value[i + 1] += value[i] / sizer;
				value[i] = value[i] % sizer;
			}
		}
		if (value.back() >= sizer) {
			value.push_back(value.back() / sizer);
			value[value.size() - 2] = value[value.size() - 2] % sizer;
		}
	}
	void mul(lol mul) {
		forin(i, value) {
			value[i] *= mul;
		}
		fori(i, value.size() - 1) {
			if (value[i] >= sizer) {
				value[i + 1] += value[i] / sizer;
				value[i] = value[i] % sizer;
			}
		}
		if (value.back() >= sizer) {
			value.push_back(value.back() / sizer);
			value[value.size() - 2] = value[value.size() - 2] % sizer;
		}
	}
	long double div(BigNum other1, BigNum other2) {
		int s = value.size();
		long double current = value.back();
		if (s >= 2) {
			current += ((long double)value[s - 2]) / sizer;
		}
		if (s >= 3) {
			current += ((long double)value[s - 3]) / (sizer * sizer);
		}
		int s1 = other1.value.size();
		int s2 = other2.value.size();
		long double other = 0;
		if (s1 + s2 - 1 == s) {
			other += other1.value.back() * other2.value.back();
			if (s1 >= 2) {
				other += ((long double)other1.value[s1 - 2] * other2.value.back()) / sizer;
			}
			if (s2 >= 2) {
				other += ((long double)other2.value[s2 - 2] * other1.value.back()) / sizer;
			}
			if (s1 >= 3) {
				other += ((long double)other1.value[s1 - 3] * other2.value.back()) / (sizer * sizer);
			}
			if (s2 >= 3) {
				other += ((long double)other2.value[s2 - 3] * other1.value.back()) / (sizer * sizer);
			}
		}
		if (s1 + s2 - 1 == s - 1) {
			other += other1.value.back() * other2.value.back();
			if (s1 >= 2) {
				other += ((long double)other1.value[s1 - 2] * other2.value.back()) / sizer;
			}
			if (s2 >= 2) {
				other += ((long double)other2.value[s2 - 2] * other1.value.back()) / sizer;
			}
			other /= sizer;
		}
		if (s1 + s2 - 1 == s - 2) {
			other += other1.value.back() * other2.value.back();
			other /= sizer * sizer;
		}
		return other / current;
	}
	string stringify() {
		string out = to_string(value.back());
		forib(i, value.size() - 1) {
			string cur = to_string(value[i] + sizer);
			out += cur.substr(1);
		}
		return out;
	}
};
lol gcd(lol a, lol b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}
lol triangle(lol x) {
	return ((x - 1) * x) / 2;
}
lol antitriangle(lol x) {
	lol low = 0, high = 2 * maxi;
	while (low < high) {
		lol mid = (low + high + 1) / 2;
		if (triangle(mid) <= x) {
			low = mid;
		}
		else {
			high = mid - 1;
		}
	}
	return low;
}
lol modInverse(lol a)
{
	lol m = maxi;
	lol y = 0, x = 1;
	while (a > 1)
	{
		lol q = a / m;
		lol t = m;
		m = a % m, a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0) {
		x += maxi;
	}
	return x;
}
lol modInverse(lol a, lol b)
{
	lol m = b;
	lol y = 0, x = 1;
	while (a > 1)
	{
		lol q = a / m;
		lol t = m;
		m = a % m, a = t;
		t = y;
		y = x - q * y;
		x = t;
	}
	if (x < 0) {
		x += b;
	}
	return x;
}
lol poww(lol a, lol b) {
	if (b == 0) {
		return 1;
	}
	if (b % 2 == 0) {
		return poww((a * a)mod, b / 2)mod;
	}
	return (a * poww((a * a)mod, b / 2))mod;
}
lol pow(lol a, lol b, lol m) {
	if (b == 0) {
		return 1;
	}
	if (b % 2 == 0) {
		return pow((a * a) % m, b / 2, m) % m;
	}
	return (a * pow((a * a) % m, b / 2, m)) % m;
}
vecl dev(vecp divisors) {
	if (divisors.size() == 0) {
		vecl cur;
		cur.push_back(1);
		return cur;
	}
	lol x = divisors.back().first;
	lol n = divisors.back().second;
	divisors.pop_back();
	vecl ans = dev(divisors);
	vecl cur;
	lol xi = 1;
	fori(i, n + 1) {
		forin(j, ans) {
			cur.push_back(ans[j] * xi);
		}
		xi *= x;
	}
	return cur;
}
bool isprime(lol a) {
	if (a == 1) {
		return false;
	}
	for (int i = 2; i * i <= a; i++) {
		if (a % i == 0) {
			return false;
		}
	}
	return true;
}
void add(veci & x, veci & y) {
	forin(i, x) {
		x[i] += y[i];
	}
}
vecl mul(vecl x, lol a) {
	forin(i, x) {
		x[i] = (x[i] * a)mod;
	}
	return x;
}
vecl add(vecl x, vecl & y) {
	forin(i, x) {
		x[i] = (x[i] + y[i])mod;
	}
	return x;
}
#define logn 18
int lca(vector<veci> & f, veci & depth, int a, int b) {
	if (depth[a] < depth[b]) {
		swap(a, b);
	}
	fori(k, logn) {
		if ((depth[a] - depth[b]) & (1 << k)) {
			a = f[k][a];
		}
	}
	if (a == b) {
		return a;
	}
	forib(k, logn) {
		if (f[k][a] != f[k][b]) {
			a = f[k][a];
			b = f[k][b];
		}
	}
	return f[0][a];
}
int tredist(vector<veci>& f, veci& depth, int a, int b) {
	return depth[a]+ depth[b]- 2*depth[lca(f,depth,a,b)];
}
struct pt
{
#define intopt(a) into(a.x) into(a.y)
#define defpt(a) pt a;intopt(a)
	lol x, y;
	lol d() const // squared length
	{
		return x * x + y * y;
	}
};
typedef vector<pt> vecpp;
inline pt operator-(const pt & a) { return { -a.x, -a.y }; }
inline pt operator+(const pt & a, const pt & b) { return { a.x + b.x, a.y + b.y }; }
inline pt operator-(const pt & a, const pt & b) { return { a.x - b.x, a.y - b.y }; }
inline lol operator*(const pt & a, const pt & b) { return a.x* b.y - a.y * b.x; } // cross product
inline bool operator<(const pt& a, const pt& b) { if (a * b != 0) return a * b < 0; return a.d() < b.d(); }
bool llll(const pt & a, const pt & b) { return a * b > 0; }
inline bool operator<=(const pt & a, const pt & b) { return a * b <= 0; }
inline lol operator/(const pt & a, const pt & b) { return a.x* b.x + a.y * b.y; } // dot product
inline bool operator==(const pt & a, const pt & b) { return a.x == b.x && a.y == b.y; } // equal
inline bool operator!=(const pt & a, const pt & b) { return a.x != b.x || a.y != b.y; } // not equal
pt o = { 0 ,0 };
bool comp(pt a, pt b) {
	if ((a - o) * (b - o) != 0)
		return (a - o) * (b - o) < 0;
	return (a - o).d() < (b - o).d();
}
bool decreasing(int a, int b) {
	return a > b;
}
#define digits 30
struct booleantree
{
	booleantree* left = NULL;
	booleantree* right = NULL;
	void add(int val) {
		booleantree* cur = this;
		forib(i, digits) {
			if ((val & (1 << i))) {
				if (cur->right == NULL) {
					cur->right = new booleantree();
				}
				cur = cur->right;
			}
			else {
				if (cur->left == NULL) {
					cur->left = new booleantree();
				}
				cur = cur->left;
			}
		}
	}
	int find(int val) {
		booleantree* cur = this;
		int ans = 0;
		forib(i, digits) {
			if ((val & (1 << i))) {
				if (cur->left == NULL) {
					cur = cur->right;
				}
				else {
					cur = cur->left;
					ans += (1 << i);
				}
			}
			else {
				if (cur->right == NULL) {
					cur = cur->left;
				}
				else {
					cur = cur->right;
					ans += (1 << i);
				}
			}
		}
		return ans;
	}
};
struct segtremin {
	vector<vecl> arr;
	int n;
	int curlogn;
	segtremin(int size, int logni) {
		n = size;
		curlogn = logni;
		arr.resize(curlogn);
		fori(i, curlogn) {
			arr[i].resize(size + 1);
		}
	}
	inline lol val(int start, int end) {
		if (end >= n) {
			end = n - 1;
		}
		if (start < 0) {
			start = 0;
		}
		lol mini = lmaxi;
		fori(i, curlogn) {
			if (start > end) {
				br
			}
			if ((end & 1) == 0) {
				min2(mini, arr[i][end]);
				end--;
				if (end < 0) {
					br
				}
			}
			if ((start & 1)) {
				min2(mini, arr[i][start])
					start++;
			}
			start /= 2;
			end /= 2;
		}
		return mini;
	}
	inline void add(int start, lol num) {
		arr[0][start] = num;
		forn(i, curlogn) {
			arr[i][start >> i] = min(arr[i - 1][(start >> i) * 2], arr[i - 1][(start >> i) * 2 + 1]);
		}
	}
};
struct segtreminplus {
	vecl arr;
	vector<vecl> arr2;
	vector<vecl> arr3;
	vector<vecl> arr4;
	int n;
	int curlogn;
	segtreminplus(int size, int logni) {
		n = size;
		curlogn = logni;
		arr.resize(size + 1);
		arr2.resize(curlogn);
		fori(i, curlogn) {
			arr2[i].resize(size + 1);
		}
		arr3.resize(curlogn);
		fori(i, curlogn) {
			arr3[i].resize(size + 1);
		}
		arr4.resize(curlogn);
		fori(i, curlogn) {
			arr4[i].resize(size + 1);
		}
	}
	inline void fixcate(int i, int j) {
		if (j < 0) {
			return;
		}
		if (i == 0) {
			arr2[i][j] = 1;
			arr3[i][j] = 1;
			arr4[i][j] = 1;
			return;
		}
		arr2[i][j] = max(arr2[i-1][2*j], arr2[i - 1][2 * j+1]);
		arr3[i][j] = arr3[i - 1][2 * j];
		arr4[i][j] = arr4[i - 1][2 * j+1];
		if (((2 * j + 1) << (i - 1)) < n && arr[((2 * j + 1) << (i - 1))] > arr[((2 * j + 1) << (i - 1)) - 1]) {
			arr2[i][j] = max(arr2[i][j], arr4[i - 1][2 * j]+ arr3[i - 1][2 * j+1]);
			if (arr2[i - 1][2 * j+1] == (1 << (i - 1))) {
				arr4[i][j] = arr4[i - 1][2 * j + 1] + arr4[i - 1][2 * j];
			}
			if (arr2[i - 1][2 * j] == (1 << (i - 1))) {
				arr3[i][j] = arr3[i - 1][2 * j + 1] + arr3[i - 1][2 * j];
			}
		}
	}
	inline lol val(int start) {
		if (start > 0) {
			return arr[start];
		}
		return arr2[curlogn-1][0];
	}
	inline void change(int start, lol num) {
		arr[start] = num;
		fori(i, curlogn) {
			fixcate(i, start >> i);
		}
	}
};
struct segtresum {
	vector<vecl> arr;
	int n;
	int curlogn;
	segtresum(int size, int logni) {
		n = size;
		curlogn = logni;
		arr.resize(curlogn);
		fori(i, curlogn) {
			arr[i].resize(size + 1);
		}
	}
	inline lol val(int start, int end) {
		/*if (end >= n) {
			end = n - 1;
		}
		if (start < 0) {
			start = 0;
		}*/
		lol mini = 0;
		fori(i, curlogn) {
			if (start > end) {
				br
			}
			if ((end & 1) == 0) {
				mini += arr[i][end];
				end--;
				if (end < 0) {
					br
				}
			}
			if ((start & 1)) {
				mini += arr[i][start];
				start++;
			}
			start /= 2;
			end /= 2;
		}
		return mini;
	}
	inline void add(int start, lol num) {
		arr[0][start] = num;
		forn(i, curlogn) {
			arr[i][start >> i] = arr[i - 1][(start >> i) * 2] + arr[i - 1][(start >> i) * 2 + 1];
		}
	}
	inline void radd(int start, lol num) {
		arr[0][start] += num;
		forn(i, curlogn) {
			arr[i][start >> i] = arr[i - 1][(start >> i) * 2] + arr[i - 1][(start >> i) * 2 + 1];
		}
	}
};
struct segtresumplus {
	vector<vecl> arr;
	vector<vecl> arrplus;
	vector<vecl> truearrplus;
	int n;
	int curlogn;
	segtresumplus(int size, int logni) {
		n = size;
		curlogn = logni;
		arr.resize(curlogn);
		fori(i, curlogn) {
			arr[i].resize(size + 1);
		}
		arrplus.resize(curlogn);
		fori(i, curlogn) {
			arrplus[i].resize(size + 1);
		}
		truearrplus.resize(curlogn);
		fori(i, curlogn) {
			truearrplus[i].resize(size + 1);
		}
	}
	inline void fix(int h, int s) {
		/*if (arrplus[h][s] == 0) {
			return;
		}
		arr[h][s] += arrplus[h][s] << h;
		if (h > 0) {
			arrplus[h - 1][2 * s] += arrplus[h][s];
			arrplus[h - 1][2 * s+ 1] += arrplus[h][s];
		}
		arrplus[h][s] = 0;*/
	}
	inline lol val(int start, int end) {
		/*if (end >= n) {
			end = n - 1;
		}
		if (start < 0) {
			start = 0;
		}*/
		forib(i, curlogn) {
			fix(i, start >> i);
			fix(i, end >> i);
		}
		lol mini = 0;
		fori(i, curlogn) {
			if (start > end) {
				br
			}
			if ((end & 1) == 0) {
				fix(i, end);
				mini += arr[i][end];
				mini += arrplus[i][end];
				fort(j, i + 1, curlogn) {
					mini += truearrplus[j][end >> (j-i)]<< i;
				}
				end--;
				if (end < 0) {
					br
				}
			}
			if ((start & 1)) {
				fix(i, start);
				mini += arr[i][start];
				mini += arrplus[i][start];
				fort(j, i + 1, curlogn) {
					mini += truearrplus[j][start >> (j - i)] << i;
				}
				start++;
			}
			start /= 2;
			end /= 2;
		}
		return mini;
	}
	inline void add(int start, lol num) {
		arr[0][start] = num;
		forn(i, curlogn) {
			arr[i][start >> i] = arr[i - 1][(start >> i) * 2] + arr[i - 1][(start >> i) * 2 + 1];
		}
	}
	inline void radd(int start,int end, lol num) {
		fori(i, curlogn) {
			if (start > end) {
				br
			}
			if ((end & 1) == 0) {
				truearrplus[i][end]+=num;
				fort(j,i, curlogn) {
					arrplus[j][end >> (j-i)] += num << i;
				}
				end--;
				if (end < 0) {
					br
				}
			}
			if ((start & 1)) {
				truearrplus[i][start] += num;
				fort(j, i, curlogn) {
					arrplus[j][start >> (j - i)] += num << i;
				}
				start++;
			}
			start /= 2;
			end /= 2;
		}
	}
};
struct unionfind{
	veci arr;
veci arr2;
int num;
unionfind(int size) {
	arr.resize(size);
	arr2.resize(size);
	num = size;
	fori(i, size) {
		arr[i] = i;
		arr2[i] = 1;
	}
}
int find(int a) {
	if (arr[a] == a) {
		return a;
	}
	return arr[a] = find(arr[a]);
}
inline void unioner(int a, int b) {
	a = find(a), b = find(b);
	if (a != b) {
		num--;
		if (arr2[a] > arr2[b]) {
			swap(a, b);
		}
		arr[a] = b;
		arr2[b] += arr2[a];
	}
}
};
string op(string s) {
	string ans;
	forinb(i, s) {
		ans.push_back(s[i]);
	}
	return ans;
}
void merge(veci& color, vector<veci>& allcolor, int l, int r) {
	if (color[l] == color[r]) {
		return;
	}
	l = color[l];
	r = color[r];
	if (allcolor[l].size() < allcolor[r].size()) {
		swap(l, r);
	}
	forin(j, allcolor[r]) {
		color[allcolor[r][j]] = l;
		allcolor[l].push_back(allcolor[r][j]);
	}
	allcolor[r].resize(0);
}
vecpp conv(vecpp a) {
	pt left = { 99999999999999,999999999999999 };
	forin(i, a) {
		if (a[i].x < left.x || a[i].x == left.x && a[i].y > left.y) {
			left = a[i];
		}
	}
	o = left;
	forin(i, a) {
		if (a[i] == left) {
			a[i] = a.back();
			a.pop_back();
			br
		}
	}
	sort(all(a), comp);
	vecpp conv(1, left);
	forin(i, a) {
		while (conv.size() > 1) {
			if ((a[i] - conv.back()) * (conv.back() - conv[conv.size() - 2]) <= 0) {
				conv.pop_back();
			}
			else {
				br
			}
		}
		conv.push_back(a[i]);
	}
	while (conv.size() > 1) {
		if ((left - conv.back()) * (conv.back() - conv[conv.size() - 2]) <= 0) {
			conv.pop_back();
		}
		else {
			br
		}
	}
	return conv;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	defn defm
		veci a(n);
	intov(a,n)
	vector<veci> primer(100000);
	vector<veci> nekt(logn, veci(n+1, n));
	fori(i, n) {
		fort(j,2, 400) {
			if (a[i] % j == 0) {
				primer[j].push_back(i);
				while (a[i] % j == 0) {
					a[i] /= j;
				}
			}
		}
		if (a[i] > 1) {
			primer[a[i]].push_back(i);
		}
	}
	forin(i, primer) {
		fori(j, ((int)primer[i].size())-1) {
			min2(nekt[0][primer[i][j]], primer[i][j + 1]);
		}
	}
	forib(i, n-1) {
		min2(nekt[0][i], nekt[0][i+1]);
		forn(j, logn) {
			nekt[j][i] = nekt[j - 1][nekt[j - 1][i]];
		}
	}
	fori(i, m) {
		defa defb
			int ans = 1;
		a--;
		int k = logn - 1;
		while (k >= 0) {
			if (nekt[k][a] < b) {
				a = nekt[k][a];
				ans += 1 << k;
			}
			else {
				k--;
			}
		}
		co ans el
	}
	ex
}