#include using namespace std; #define REP(i,n) for(ll i=0;i<(ll)(n);i++) #define ALL(x) (x).begin(),(x).end() #define IO ios::sync_with_stdio(false),cin.tie(nullptr); #define LB(v,x) (int)(lower_bound(ALL(v),x)-(v).begin()) #define UQ(v) sort(ALL(v)), erase(unique(ALL(v)),v.end()) template bool chmax(T&a, const T&b){ if(a bool chmin(T&a, const T&b){ if(b using rpriority_queue=priority_queue,greater>; using ll=long long; const int INF=1e9+10; const ll INFL=4e18; using VI=vector; using VVI=vector; using VL=vector; using VVL=vector; using VS=vector; using PL=pair; using VP=vector; using TL=tuple; using WG=vector>>; /// @file mst.hpp /// @brief マージソート木 template struct MergeSortTree{ MergeSortTree()=default; /// @brief 配列 v からマージソート木を構築する MergeSortTree(const vector&v){ n=v.size(); mx=*max_element(v.begin(),v.end()),mn=*min_element(v.begin(),v.end()); dat=vector>(n<<1); for(int i=0;i0;i--){ merge( dat[i<<1].begin(),dat[i<<1].end(), dat[i<<1|1].begin(),dat[i<<1|1].end(), back_inserter(dat[i])); } } /// @brief 区間 [l, r) に存在する val 未満の値の個数を返す /// @note O(log(N)^2) int count_lt(int l,int r,T val){ l+=n,r+=n; int ret=0; while(l>=1,r>>=1; } return ret; } /// @brief 区間 [l, r) に存在する val 以下の値の個数を返す /// @note O(log(N)^2) int count_le(int l,int r,T val){return count_lt(l,r,val+1);} /// @brief 区間 [l, r) に存在する val より大きい値の個数を返す /// @note O(log(N)^2) int count_gt(int l,int r,T val){return n-l-count_le(l,r,val);} /// @brief 区間 [l, r) に存在する val 以上の値の個数を返す /// @note O(log(N)^2) int count_ge(int l,int r,T val){return n-l-count_lt(l,r,val);} /// @brief 区間 [l, r) の小さい方から k 番目の値を返す /// @brief k は 1-indexed で与える /// @note O(log(N)^3) T kth(int l,int r,int k){ T lo=mn-1,hi=mx+1; while(hi-lo>1){ T mid=(hi+lo)/2; (count_lt(l,r,mid)>=k?hi:lo)=mid; } return lo; } private: int n; vector>dat; int search(int i,T val){return lower_bound(dat[i].begin(),dat[i].end(),val)-dat[i].begin();} T mx,mn; }; int main(){ IO; const int mx=1e6+10; VL md(mx,1); for(ll i=2;imst(md); int Q;cin>>Q; while(Q--){ int l,r;cin>>l>>r;r++; if(l==1) cout<<1<<'\n'; else cout<