const vector<vector> M = { {21,1,0,0,0,0}, {5,21,2,0,0,0}, {0,4,21,3,0,0}, {0,0,3,21,4,0}, {0,0,0,2,21,5}, {0,0,0,0,1,21} };

const vector<vector> I = { {1,0,0,0,0,0}, {0,1,0,0,0,0}, {0,0,1,0,0,0}, {0,0,0,1,0,0}, {0,0,0,0,1,0}, {0,0,0,0,0,1}, };

const int MOD = 1e9 + 7;

vector<vector> multiply(vector<vector> a,vector<vector> b){ vector<vector> c(6,vector(6,0)); for(int i = 0; i < 6; ++i) for(int j = 0; j < 6; ++j) for(int k = 0; k < 6; ++k) c[i][j] += a[i][k] * b[k][j], c[i][j] %= MOD; return c; }

vector<vector> power(int N){

vector<vector> ret = I, a = M;

while(N > 0){ if(N&1) ret = multiply(ret,a); N /= 2; a = multiply(a,a); }

return ret; }

int solve(int N){

auto M = power(N);

return M[5][0];

}

I was only able to solve 250 pointer using Matrix exponentiation, 150 pointer seemed like DP but was not able to implement. I have no idea about 200 pointer.

#include <bits/stdc++.h>
#define int int64_t //be careful about this 

using namespace std;

namespace IN{
  template<class T> void read(vector<T> &A);
  template<class S,class T> void read(pair<S,T> &A);
  template<class T,size_t N> void read(array<T,N> &A);

  template<class T> void read(T& x){ 
    cin >> x;}
  template<class H, class... T> void read(H& h, T&... t){ 
    read(h); read(t...);}

  template<class T> void read(vector<T> &A){ 
    for(auto& x : A) read(x);}
  template<class S,class T> void read(pair<S,T> &A){ 
      read(A.first); read(A.second);}
  template<class T,size_t N> void read(array<T,N> &A){
    for(int i = 0; i < N; ++i)  read(A[i]);}
}

namespace OUT{
  template<typename T>
  void __p(T a) {
    cout<<a; 
  }
  template<typename T, typename F>
  void __p(pair<T, F> a) {
    cout<<"{";
    __p(a.first);
    cout<<",";
    __p(a.second);
    cout<<"}\n"; 
  }
  template<typename T, size_t N>
  void __p(array<T,N> a){
    cout<<"{";
    for(int i = 0; i < N; ++i)
      __p(a[i]),cout<<",}\n"[i+1==N];
  }
  template<typename T>
  void __p(std::vector<T> a) {
    cout<<"{";
    for(auto it=a.begin(); it<a.end(); it++)
      __p(*it),cout<<",}\n"[it+1==a.end()]; 
  }
  template<typename T, typename ...Arg>
  void __p(T a1, Arg ...a) {
    __p(a1);
    __p(a...);
  }
  template<typename Arg1>
  void __f(const char *name, Arg1 &&arg1) {
    cout<<name<<" : ";
    __p(arg1);
    cout<<endl;
  }
  template<typename Arg1, typename ... Args>
  void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    int bracket=0,i=0;
    for(;; i++)
      if(names[i]==','&&bracket==0)
        break;
      else if(names[i]=='(')
        bracket++;
      else if(names[i]==')')
        bracket--;
    const char *comma=names+i;
    cout.write(names,comma-names)<<" : ";
    __p(arg1);
    cout<<" | ";
    __f(comma+1,args...);
  }
  #define trace(...) cout<<"Line:"<<__LINE__<<"  ", __f(#__VA_ARGS__, __VA_ARGS__)
}


namespace FUN{
  void IO(string s = ""){
    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.precision(20); 
    cout << fixed;
    if(!s.empty()){
      freopen((s+".in").c_str(),"r",stdin);
      freopen((s+".out").c_str(),"w",stdout);
    }
  }

  const auto start_time = chrono::high_resolution_clock::now();
  void output_run_time(){
    // will work for ac,cc&&cf.
  #ifndef ONLINE_JUDGE
    auto end_time = chrono::high_resolution_clock::now();
    chrono::duration<double> diff = end_time-start_time;
      cout << "\n\n\nTime Taken : " << diff.count();
  #endif
  }

  template<class T> bool ckmin(T& a, const T b) { return b < a ? a = b, 1 : 0;}
  template<class T> bool ckmax(T& a, const T b) { return a < b ? a = b, 1 : 0;}
}


using namespace IN;
using namespace OUT;
using namespace FUN;



















template<class T> 
struct basic_segment_tree { 
  const T ID =  0;
  T comb(T a, T b){// comb(ID,b) = b
    return __gcd(a,b);
  }
  int n; vector<T> seg;
  void init(int _n){
    n = _n; seg.assign(2 * n,ID);
  }
  void pull(int p){
    seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
  }
  void upd(int p, T val){ // update val at position p
    seg[p += n] = val;
    for(p /= 2; p; p /= 2) pull(p);
  }
  T query(int l, int r){ // query on interval [l, r]
    T ra = ID, rb = ID;
    for(l += n, r += n+1; l < r; l /= 2, r /= 2){
      if(l&1) ra = comb(ra,seg[l++]);
      if(r&1) rb = comb(seg[--r],rb);
    }
    return comb(ra,rb);
  }
};

template<typename T>
struct fenwick_tree{
  int tree_n = 0;
  T tree_sum = 0;
  vector<T> tree;
 
  fenwick_tree(int n = -1){
    if(n >= 0)
      init(n);
  }
 
  static int highest_bit(int x){
    return x == 0 ? -1 : 31 - __builtin_clz(x);
  }
 
  void init(int n) {
    tree_n = n;
    tree_sum = 0;
    tree.assign(tree_n + 1, 0);
  }
 
  // O(n) initialization of the Fenwick tree.
  template<typename T_array>
  void build(const T_array &initial){
    assert(int(initial.size()) == tree_n);
    tree_sum = 0;

    for(int i = 1; i <= tree_n; i++){
      tree[i] = initial[i-1];
      tree_sum += initial[i-1];
      for(int k = (i & -i) >> 1; k > 0; k >>= 1)
        tree[i] += tree[i - k];
    }
  }
 
  // index is in [0, tree_n).
  void update(int index, const T &change){
    assert(0 <= index && index < tree_n);
    tree_sum += change;

    for(int i = index + 1; i <= tree_n; i += i & -i)
      tree[i] += change;
  }
 
  // Returns the sum of the range [0, count).
  T query(int count) const {
    count = min(count, tree_n);
    T sum = 0;
    for(int i = count; i > 0; i -= i & -i)
      sum += tree[i];
    return sum;
  }
 
  // Returns the sum of the range [start, tree_n).
  T query_suffix(int start) const {
    return tree_sum - query(start);
  }
 
  // Returns the sum of the range [a, b).
  T query(int a, int b) const {
    return query(b) - query(a);
  }
 
  // Returns the element at index a in O(1) amortized across every index. Equivalent to query(a, a + 1).
  T get(int a) const {
    assert(0 <= a && a < tree_n);
    int above = a + 1;
    T sum = tree[above];
    above -= above & -above;
    while (a != above){
      sum -= tree[a];
      a -= a & -a;
    }
    return sum;
  }
 
  bool set(int index, T value){
    assert(0 <= index && index < tree_n);
    T current = get(index);

    if(current == value)
      return false;

    update(index, value - current);
    return true;
  }
 
  // Returns the largest p in `[0, tree_n]` such that `query(p) <= sum`. Returns -1 if no such p exists (`sum < 0`).
  // Can be used as an ordered set/multiset on indices in `[0, tree_n)` by using the tree as a 0/1 or frequency array:
  // `set(index, 1)` is equivalent to insert(index). `update(index, +1)` is equivalent to multiset.insert(index).
  // `set(index, 0)` or `update(index, -1)` are equivalent to erase(index).
  // `get(index)` provides whether index is present or not, or the count of index (if multiset).
  // `query(index)` provides the count of elements < index.
  // `find_last_prefix(k)` finds the k-th smallest element (0-indexed). Returns `tree_n` for `sum >= set.size()`.
  int find_last_prefix(T sum) const {
    if(sum < 0)
      return -1;

    int prefix = 0;

    for(int k = highest_bit(tree_n); k >= 0; k--)
      if(prefix + (1 << k) <= tree_n && tree[prefix + (1 << k)] <= sum){
        prefix += 1 << k;
        sum -= tree[prefix];
      }

    return prefix;
  }
};
 

signed main(){
  IO();

  int n;
  read(n);
  vector<int> a(n);
  read(a);

  basic_segment_tree<int> st;
  st.init(n);
  for(int i = 0; i < n; ++i)
    st.upd(i,a[i]);

  vector<int> ends(n,-1);
  for(int i = 0; i < n; ++i){
    int lo = i, hi = n;
    while(hi - lo > 1){
      int mid = (hi + lo)/2;
      st.query(i,mid) - (mid - i + 1) >= 0 ? lo = mid : hi = mid;
    }
    if(st.query(i,lo) == (lo - i + 1))
      ends[lo] = i;
  }


  fenwick_tree<int> ft;
  ft.init(n);

  int ans = 0;
  for(int i = 0; i < n; ++i){
    if(ends[i] >= 0 && ft.query(ends[i],i) == 0){
      ++ans;
      ft.update(i,1);
    }
    cout << ans << " ";
  }



  output_run_time();
  return 0;
}
















 

#include<bits/stdc++.h>
#define f_in(s) freopen(s,"r",stdin)
#define f_out(s) freopen(s,"w",stdout)
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll
#define rep(i,a,n) for(int i=(a),__##i=(n);i<=__##i;++i)
#define repe(i,a,n) for(int i=(a),__##i=(n);i<__##i;++i)
#define repv(i,n,a) for(int i=(n),__##i=(a);i>=__##i;--i)
#define repl(i,a,n) for(ll i=(a),__##i=(n);i<=__##i;++i)
#define lowbit(x) ((x)&-(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define mcpy(x,y) memcpy(x,y,sizeof(x))
#define popcount __builtin_popcount
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<db,db>
#define X first
#define Y second
#define LL __int128
#define ll long long
#define ull unsigned long long
#define db double
using namespace std;
mt19937_64 rndGen(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l,r) uniform_int_distribution<int>(l,r)(rndGen)
#define rll(l,r) uniform_int_distribution<ll>(l,r)(rndGen)
#define rreal(l,r) uniform_real_distribution<double>(l,r)(rndGen)

// #define HDU
inline ll read(){
#ifdef HDU
    ll ret; scanf("%lld",&ret);
    return ret;
#else
    ll s=0,f=1; char c=getchar();
    while(c<'0'||c>'9') f*=c=='-'?-1:1,c=getchar();
    while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
    return s*f;
#endif
}
template<class T> inline void cmax(T &a,T b){ a=max(a,b); }
template<class T> inline void cmin(T &a,T b){ a=min(a,b); }

const ll P=998244353;
inline ll pw(ll a,ll x=P-2){
    ll ret=1;
    for(;x;x>>=1,a=a*a%P) if(x&1) ret=ret*a%P;
    return ret;
}

struct BIT{
    int n;
    vector<ll> c;
    BIT(int n):n(n),c(n){}
    void add(int x,ll v){
        while(x<n) c[x]+=v,x+=lowbit(x);
    }
    ll sum(int x){
        ll ret=0;
        while(x) ret+=c[x],x-=lowbit(x);
        return ret;
    }
};


inline void wk(){
    ll a=read(),b=read(),mb=(1<<__lg(b))*2;
    ll ans=infl;
    repe(i,b,mb){
        if(a>i) continue;
        ll ma=a;
        while((ma&i)!=ma) ma+=lowbit(ma);
        cmin(ans,ma-a+(ma!=b)+i-b);
    }
    printf("%lld\n",ans);
}

int main(){
    repe(_,0,read()) wk();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long

int t, n, m, k, a, b, mod = (1 << 20);
string s;
mt19937_64 rng;

int mul(int x, int y){
    if(y == 0) return 1;
    int ans = mul(x, y / 2);
    if(y % 2 == 0) return (ans * ans) % mod;
    else return (((ans * ans) % mod) * x) % mod;
}

void solve(){  
    int ans = b - a;
    int A = a;
    while(A <= b){
        int q = (A | b);
        if(q <= b) ans = min(ans, A - a + 1 + b - q); 
        A++;
    }
    int B = b, o = 1;
    while(o < b) o = o * 2 + 1;
    while(B <= o){
        int q = (a | B); 
        if(q == B) ans = min(ans, B - b + 1);
        B++;
    }
    cout << ans << "\n";
}

signed main(){
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
    rng.seed((int)main ^ time(0));
    #ifdef Kawaii
        auto starttime = chrono::high_resolution_clock::now();
    #endif

    cin >> t;
    while(t--){
        cin >> a >> b; 
        solve();
    }

    #ifdef Kawaii
        auto endtime = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count(); 
        cout << "\n=====" << "\nUsed: " << duration << " ms\n";
    #endif
}

#include<bits/stdc++.h>
#define lp long long
#define ulp unsigned long long
#define pa pair < lp , lp >
#define fi first
#define se second
#define mp make_pair
#define ls x<<1
#define rs x<<1|1
#define kp push_back
#define db double
#define itn insert
#define pc putchar
#define rep(i,x,y) for(lp i=(x);i<=(y);i++)
#define per(i,x,y) for(lp i=(x);i>=(y);i--)
using namespace std;

inline lp read(){
    lp r=0,f=0;char c=getchar();
    while(!isdigit(c))f=c=='-',c=getchar();
    while(isdigit(c))r=r*10+(c^48),c=getchar();
    return f?-r:r;
}

inline lp minn(lp a,lp b){return a<b?a:b;}
inline lp maxx(lp a,lp b){return a>b?a:b;}

//inline lp sqt(lp x){lp res=sqrt(x)+1;while(res*res>x)res--;return res;}

lp gcd(lp a,lp b){return !b?a:gcd(b,a%b);}
lp lcm(lp a,lp b){return a/gcd(a,b)*b;}

void wr(lp x){if(x<0)x=-x,pc('-');if(x>9)wr(x/10);pc(x%10+'0');}

const lp ml=1e6+101;
const lp inf=1e15;
//const lp mk=+101;
//const lp mo=1e9+7;
//const lp mo=998244353;

lp t,n,m,q;
lp ans;

lp x[ml],ins[ml];
//pa a[ml];
char s[ml];
//string s;
//vector < lp > e[ml];
//map < lp , lp > atl;
//multiset < lp > s;





//---------------------------------------------------------------------------------------------------
//lp qpow(lp x,lp y=mo-2){lp res=1;while(y){if(y&1)res=res*x%mo;x=x*x%mo;y>>=1;}return res;}

/*
lp fac[ml],inv[ml];

void init_C(lp l){
    fac[0]=inv[0]=1;
    for(lp i=1;i<=l;i++)fac[i]=fac[i-1]*i%mo;
    inv[l]=qpow(fac[l]);
    for(lp i=l-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mo;
}

lp C(lp a,lp b){
	if(a<0||b<0||a<b)return 0;
	return fac[a]*inv[b]%mo*inv[a-b]%mo;
}
*/
//---------------------------------------------------------------------------------------------------




//---------------------------------------------------------------------------------------------------
/*
struct BIT{
    lp sz[ml];

    lp query(lp x){lp res=0;for(;x>=1;x-=x&-x)res+=sz[x];return res;}

    void modify(lp x,lp y=1){for(;x<=n;x+=x&-x)sz[x]+=y;}
}str;
*/
//----------------------------------------------------------------------------------------------------






//----------------------------------------------------------------------------------------------------
/*
-----------------------------------------------------------------------------------
鍔ㄦ€佸紑鐐?鍖洪棿淇敼&鏈€灏忓€?灏佽 鏉庤秴绾挎鏍?

auther:wuxingzhi

浣跨敤鍓嶏細init(鍊煎煙)锛屾敼ML	

鍑芥暟锛歁odify,Query,init

Ps:姹傛渶澶у€肩洿鎺ユ妸涓変釜">"鏀规垚"<"锛屾妸鈥渞eturn inf"鏀规垚"return -inf"锛屾妸"minn"鏀规垚"maxx"
-----------------------------------------------------------------------------------
*/
/*
struct Lc{
#define lo lson[x]
#define ro rson[x]

	static const lp ML=1e6+101;
	const lp inf=1e15;
	
	lp N,tot;
	
	lp lson[ML<<2],rson[ML<<2],k[ML<<2],b[ML<<2],vis[ML<<2];
	
	lp calc(lp x,lp k,lp b){return x*k+b;}
	
	void init(lp Num){N=Num;for(lp i=1;i<=tot;i++)lson[i]=rson[i]=k[i]=b[i]=vis[i]=0;tot=1;}
	
	lp modify(lp qk,lp qb,lp ql,lp qr,lp x,lp l,lp r){
		if(!x)x=++tot;
		lp mid=(l+r)>>1;
		if(ql<=l&&qr>=r){
			if(!vis[x]){vis[x]=1,k[x]=qk,b[x]=qb;return x;}
			if(calc(mid,k[x],b[x])>calc(mid,qk,qb))swap(qk,k[x]),swap(qb,b[x]);
			if(calc(l,k[x],b[x])>calc(l,qk,qb))lo=modify(qk,qb,ql,qr,lo,l,mid);
			if(calc(r,k[x],b[x])>calc(r,qk,qb))ro=modify(qk,qb,ql,qr,ro,mid+1,r);
			return x;
		}
		if(ql<=mid)lo=modify(qk,qb,ql,qr,lo,l,mid);
		if(qr>mid)ro=modify(qk,qb,ql,qr,ro,mid+1,r);
		return x;
	}
	
	lp query(lp d,lp x,lp l,lp r){
		if(!vis[x]||!x)return inf;
		lp res=calc(d,k[x],b[x]),mid=(l+r)>>1;
		if(l==r)return res;
		if(d<=mid)return minn(res,query(d,lo,l,mid));
		else return minn(res,query(d,ro,mid+1,r));
	}
	
	void Modify(lp k,lp b,lp l=-1,lp r=-1){l==-1?modify(k,b,0,N,1,0,N):modify(k,b,l,r,1,0,N);}
	
	lp Query(lp d){return query(d,1,0,N);}
	
#undef lo
#undef ro
}t;
*/
//-----------------------------------------------------------------------------------------------------------

int main(){
    cin>>t;
    while(t--){
		cin>>n>>m;
		if(n>=m)cout<<n-m<<'\n';
		else{
			ans=m-n;
			for(lp i=n;i<=m;i++)if(((i^m)&i)==0){ans=minn(ans,i-n+1);break;}
			for(lp i=m;i;i++)if(((n^i)&n)==0){ans=minn(ans,i-m+1);break;}
			cout<<ans<<'\n';
		}
    }
return 0;
}

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<random>
#include<chrono>
#include<deque>
#include<cassert>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define mp std::make_pair
#define ulf Useful_little_function
#define abs ccf
#define inline __attribute__((always_inline))inline
#define INF (0x3f3f3f3f)
#define INT_INF (2147483647)
#define LLINF (0x3f3f3f3f3f3f3f3fll)
#define LL_INF (9223372036854775807)
#define memset __builtin_memset
#define popcount __builtin_popcount
std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
typedef long long ll;
typedef std::pair<int,int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
inline void file(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
namespace IO{
    #define BUF_SIZE (1<<16)
    #define OUT_SIZE (1<<16)
    bool IOerror=0;
    inline char nc(){static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;if(p1==pend){p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);if(pend==p1)return IOerror=1,-1;}return *p1++;}
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
    inline void read(ll &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
    inline void read(double &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;}
    inline void read(char *s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;}
    inline void read(char &c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return;}}
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        inline void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;}
        inline void print(int x){static char s[15],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void println(int x){print(x);out('\n');}
        inline void print(ll x){static char s[25],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void println(ll x){print(x);out('\n');}
        inline void print(double x,int y){//y<18
			static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if(x<-1e-12)out('-'),x=-x;x*=mul[y];ll x1=(ll)floor(x);if(x-floor(x)>=0.5)++x1;ll x2=x1/mul[y],x3=x1-x2*mul[y];print(x2);if(y>0){out('.');for(size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i);print(x3);}
        }
        inline void println(double x,int y){print(x,y);out('\n');}
        inline void print(char *s){while(*s)out(*s++);}
        inline void println(char *s){while(*s)out(*s++);out('\n');}
        inline void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    #undef OUT_SIZE
    #undef BUF_SIZE
}using namespace IO;
namespace Little_function{
	inline int abs(int x){return x<0?-x:x;}
	inline ll abs(ll x){return x<0?-x:x;}
	inline double abs(double x){return x<0?-x:x;}
	inline int max(const int &a,const int &b){return a>b?a:b;}
	inline ll max(const ll &a,const ll &b){return a>b?a:b;}
	inline double max(const double &a,const double &b){return a>b?a:b;}
	inline int min(const int &a,const int &b){return a<b?a:b;}
	inline ll min(const ll &a,const ll &b){return a<b?a:b;}
	inline double min(const double &a,const double &b){return a<b?a:b;}
	inline void swap(int &x,int &y){x^=y^=x^=y;}
	inline void swap(ll &x,ll &y){x^=y^=x^=y;}
	inline void swap(double &x,double &y){double t=x;x=y,y=t;}
	inline int madd(const int &a,const int &b,const int &p){return (a+b)%p;}
	inline int mdel(const int &a,const int &b,const int &p){return (a-b<0?a-b+p:a-b);}
	int gcd(int a,int b){return !b?a:gcd(b,a%b);}
	ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
}using namespace Little_function;
int main(){int T;read(T);while(T--){
	int a,b;read(a),read(b);
	int ans=b-a;
	for(int i=0;i<b-a;++i){
		bool flag=0;int x=0;
		for(int j=19;j>=0;--j){
			int c=(((a+i)>>j)&1);
			int d=((b>>j)&1);
			if(c){
				x|=(1<<j);
				if(!d&&!flag) flag=1;
			}
			else if(!flag&&d) x|=(1<<j);
		}
		ans=min(ans,i+1+x-b);
	}
	println(ans);
}
	return 0;
}

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define ld long double
#define pll pair<long long, long long>
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define vpll vector<pair<long long, long long>>
#define vec vector
#define indexed_set                                          \
    tree<long long, null_type, less<long long>, rb_tree_tag, \
         tree_order_statistics_node_update>

#define FOR(i, s, e) for (long long i = s; i < e; i++)
#define CFOR(i, s, e) for (long long i = s; i <= e; i++)
#define RFOR(i, e, s) for (long long i = e - 1; i >= s; i--)
#define TRAV(a, c) for (auto a : c)
#define ITER(it, cs, ce) for (auto it = cs; it != ce; it++)
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl
mt19937_64 rng(100);

template <class T>
string to_string(vector<T> &vec) {
    std::ostringstream vts;
    if (!vec.empty()) {
        std::copy(vec.begin(), vec.end() - 1,
                  std::ostream_iterator<T>(vts, ", "));
        vts << vec.back();
    }
    return "[" + vts.str() + "]";
}

#define MOD 1000000007

#define FASTIO ;
#define PRECISION ;
//#define FILE ;

//#define SINGLE ;
#define MULTIPLE ;
//#define GOOGLE ;

void solve() {
    ll a, b;
    cin >> a >> b;
    if (a == b) {
        cout << "0\n";
        return;
    }
    if ((a | b) == b) {
        cout << "1\n";
        return;
    }
    ll ans = b - a;
    CFOR(i, 0, b - a) {
        if (((a + i) | b) == b) {
            ans = min(ans, i + 1);
            break;
        }
    }
    FOR(i, 0, 1000000) {
        if ((a | (b + i)) == (b + i)) {
            ans = min(ans, i + 1);
            break;
        }
    }
    cout << ans << "\n";

    // if (a == b) {
    //     cout << "0\n";
    //     return;
    // }
    // if ((a | b) == b) {
    //     cout << "1\n";
    //     return;
    // }
    // ll ans = LLONG_MAX;
    // RFOR(i, 30, 0) {
    //     if ((a & (1ll << i)) && !(b & (1ll << i))) {
    //         ll na = 0;
    //         ll nb = 0;
    //         RFOR(j, i + 1, 0) {
    //             if (a & (1ll << j)) {
    //                 na |= (1ll << j);
    //             }
    //             if (b & (1ll << j)) {
    //                 nb |= (1ll << j);
    //             }
    //         }
    //         cerr << na << " " << nb << "\n";
    //         ans = min(ans, na - nb + 1);
    //         break;
    //     }
    //     if (!(a & (1ll << i)) && (b & (1ll << i))) {
    //         if ((1ll << i) == b) {
    //             ans = min(ans, (1ll << i) - a);
    //         } else {
    //             ans = min(ans, (1ll << i) - a + 1);
    //         }
    //     }
    // }
    // cout << ans << "\n";
}

int main() {
#ifdef FASTIO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#endif
#ifdef PRECISION
    cout << fixed << setprecision(10);
#endif
#ifdef FILE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
#ifdef SINGLE
    solve();
#endif
#ifdef MULTIPLE
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        solve();
    }
#endif
#ifdef GOOGLE
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        solve();
    }
#endif
}

#define A3F 0x7f7f7f7f,
#define A3E 0x7f7f7f7f;
#define A3D main(void)
#define A3C ++tmpans;
#define A3B namespace
#define A3A min(ans,
#define A39 min(ret,
#define A38 tmpans);
#define A37 tmpans
#define A36 endl;
#define A35 (T--)
#define A34 using
#define A33 while
#define A32 (((t
#define A31 (int
#define A30 (ret
#define A2F cout
#define A2E ++i)
#define A2D --k)
#define A2C else
#define A2B k));
#define A2A std;
#define A29 ans
#define A28 b);
#define A27 20;
#define A26 cin
#define A25 for
#define A24 int
#define A23 ret
#define A22 k);
#define A21 a)
#define A20 a,
#define A1F ==
#define A1E b)
#define A1D b;
#define A1C a;
#define A1B !=
#define A1A i;
#define A19 if
#define A18 (1
#define A17 (i
#define A16 k)
#define A15 (t
#define A14 +=
#define A13 0)
#define A12 0;
#define A11 1)
#define A10 <<
#define AF <=
#define AE >=
#define AD >>
#define AC T,
#define AB T;
#define AA +
#define A9 a
#define A8 k
#define A7 &
#define A6 t
#define A5 =
#define A4 i
#define A3 b
#define A2 -
#define A1 {
#define A0 }
#include <bits/stdc++.h>
#define A40 A34 A3B A2A A24 A3D A1 A24 AC A29 A5
#define A41 A3E A26 AD AB A33 A35 A1 A24 A20 A1D
#define A42 A26 AD A9 AD A1D A29 A5 A3 A2 A1C
#define A43 A25 A31 A4 A5 A1C A4 AF A1D A2E A1
#define A44 A24 A23 A5 A3F A6 A5 A1A A25 A31 A8
#define A45 A5 A27 A8 AE A12 A2D A1 A19 A32 AD
#define A46 A16 A7 A11 A1F A13 A1 A19 A15 AA A18
#define A47 A10 A16 AE A1E A1 A23 A5 A39 A6 AA
#define A48 A18 A10 A2B A0 A2C A1 A6 A14 A18 A10
#define A49 A22 A0 A0 A0 A24 A37 A5 A17 A2 A21
#define A4A AA A30 A2 A28 A19 A17 A1B A1E A3C A29
#define A4B A5 A3A A38 A0 A2F A10 A29 A10 A36 A0
#define A4C A0 
#define A4D A40 A41 A42 A43 A44 A45 A46 A47 A48 A49
#define A4E A4A A4B A4C 
#define A4F A4D A4E 
#define A50(__FOX__) __FOX__
A50(A4F)

#include <bits/stdc++.h>

// #pragma GCC optimize("O3")

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Size(a) (int)a.size()
#define ll long long
#define ld long double

// #define int long long

using namespace std;

void solve() {
    int a, b;
    cin >> a >> b;

    if ((a | b) == b) {
        cout << "1\n";
        return;
    }

    int ans = b - a;
    for (int k = b; k <= 2 * b + 100; k++) {
        int val = k - b + 1;
        if ((a | k) != k) {
            int cur = 1e9;
            for (int i = 21; i >= 0; i--) {
                if (((a >> i) & 1) == 0 && ((k >> i) & 1))
                    cur = min(cur, (1 << i) - (a & (1 << (i)) - 1));
                if (((a >> i) & 1) && !((k >> i) & 1)) {
                    // j = i;
                    break;
                }
            }
            val += cur;
            // assert(j != -1);
            // val -= (a & ((1 << (j + 1)) - 1));
            // while (((k >> j) & 1) == 0)
            //     j++;
            // val += (1 << j);
        }
        ans = min(ans, val);
    }
    cout << ans << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    #ifdef DIMSS
        freopen("test.txt", "r", stdin);
    #endif

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
        #ifdef DIMSS
            cerr << "--------\n";
        #endif
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define Jay_JAGANATH ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long 
#define lld long long double
#define sz(a) int((a).size())
#define endl '\n' 
#define all(x) (x).begin(), (x).end()
#define pb push_back 
#define ppb pop_back
#define mp make_pair 
#define ff first   
#define ss second
#define INF 1e18   
ll mod = 1e9+7;
ll MOD = 998244353;

vector<int> v;

void solve() {
    int a, b;
    cin >> a >> b;
    int ans = b - a;
    int x = a;
    while(x <= b) {
        int t = x | b;
        int c = x - a + 1 + t - b;
        ans = min(ans, c);  
        x++;
    }
    x = b;
    int lim = b + b - a;

    while(x <= lim) {
        int t = x | a;
        int c = x - b + 1 + t - x;
        ans = min(c, ans);
        x++;
    }
    cout << ans << endl;
}
 
int32_t main() {
    Jay_JAGANATH;   
    cout.tie(NULL);
    int t=1;
    cin >> t;
    for(int i=0;i<31;i++) {
        v.pb(pow(2, i));
    }
    while(t--) {
        solve();
    }
    #ifndef ONLINE_JUDGE
        cerr << "\nTime: " << (float)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
    #endif
} 
/*
 
*/

#include<bits/stdc++.h>
#define f_in(s) freopen(s,"r",stdin)
#define f_out(s) freopen(s,"w",stdout)
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3fll
#define rep(i,a,n) for(int i=(a),__##i=(n);i<=__##i;++i)
#define repe(i,a,n) for(int i=(a),__##i=(n);i<__##i;++i)
#define repv(i,n,a) for(int i=(n),__##i=(a);i>=__##i;--i)
#define repl(i,a,n) for(ll i=(a),__##i=(n);i<=__##i;++i)
#define lowbit(x) ((x)&-(x))
#define mset(x,v) memset(x,v,sizeof(x))
#define mcpy(x,y) memcpy(x,y,sizeof(x))
#define popcount __builtin_popcount
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<db,db>
#define X first
#define Y second
#define LL __int128
#define ll long long
#define ull unsigned long long
#define db double
using namespace std;
mt19937_64 rndGen(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l,r) uniform_int_distribution<int>(l,r)(rndGen)
#define rll(l,r) uniform_int_distribution<ll>(l,r)(rndGen)
#define rreal(l,r) uniform_real_distribution<double>(l,r)(rndGen)

// #define HDU
inline ll read(){
#ifdef HDU
    ll ret; scanf("%lld",&ret);
    return ret;
#else
    ll s=0,f=1; char c=getchar();
    while(c<'0'||c>'9') f*=c=='-'?-1:1,c=getchar();
    while(c>='0'&&c<='9') s=s*10+c-'0',c=getchar();
    return s*f;
#endif
}
template<class T> inline void cmax(T &a,T b){ a=max(a,b); }
template<class T> inline void cmin(T &a,T b){ a=min(a,b); }

const ll P=998244353;
inline ll pw(ll a,ll x=P-2){
    ll ret=1;
    for(;x;x>>=1,a=a*a%P) if(x&1) ret=ret*a%P;
    return ret;
}

struct BIT{
    int n;
    vector<ll> c;
    BIT(int n):n(n),c(n){}
    void add(int x,ll v){
        while(x<n) c[x]+=v,x+=lowbit(x);
    }
    ll sum(int x){
        ll ret=0;
        while(x) ret+=c[x],x-=lowbit(x);
        return ret;
    }
};


inline void wk(){
    int n=read();
    vector<ll> a(n);
    repe(i,0,n) a[i]=read();
    vector<int> ans(n);

    vector<vector<ll>> st(20,vector<ll>(n));
    repe(i,0,n) st[0][i]=a[i];
    repe(s,0,19) repe(i,0,n-(1<<s)){
        st[s+1][i]=__gcd(st[s][i],st[s][i+(1<<s)]);
    }
    auto gcd=[&](int l,int r){
        int d=__lg(r-l+1);
        return __gcd(st[d][l],st[d][r-(1<<d)+1]);
    };

    vector<int> idx(n+1);
    iota(idx.begin(),idx.end(),0);
    int l=0;
    repe(r,0,n){
        if(a[r]==1){
            ans[r]=1,l=r+1;
            continue;
        }
        int x=*lower_bound(idx.begin(),idx.begin()+r,0,[&](int i,int _){
            return gcd(i,r)<r-i+1;
        });
        if(x<l) continue;
        if(gcd(x,r)==r-x+1) ans[r]=1,l=r+1;
    }

    repe(i,1,n) ans[i]+=ans[i-1];
    repe(i,0,n) printf("%d ",ans[i]);
}

int main(){
    repe(_,0,1) wk();
    return 0;
}

#include <bits/stdc++.h>
#define int int64_t //be careful about this 

using namespace std;

namespace IN{
  template<class T> void read(vector<T> &A);
  template<class S,class T> void read(pair<S,T> &A);
  template<class T,size_t N> void read(array<T,N> &A);

  template<class T> void read(T& x){ 
    cin >> x;}
  template<class H, class... T> void read(H& h, T&... t){ 
    read(h); read(t...);}

  template<class T> void read(vector<T> &A){ 
    for(auto& x : A) read(x);}
  template<class S,class T> void read(pair<S,T> &A){ 
      read(A.first); read(A.second);}
  template<class T,size_t N> void read(array<T,N> &A){
    for(int i = 0; i < N; ++i)  read(A[i]);}
}

namespace OUT{
  template<typename T>
  void __p(T a) {
    cout<<a; 
  }
  template<typename T, typename F>
  void __p(pair<T, F> a) {
    cout<<"{";
    __p(a.first);
    cout<<",";
    __p(a.second);
    cout<<"}\n"; 
  }
  template<typename T, size_t N>
  void __p(array<T,N> a){
    cout<<"{";
    for(int i = 0; i < N; ++i)
      __p(a[i]),cout<<",}\n"[i+1==N];
  }
  template<typename T>
  void __p(std::vector<T> a) {
    cout<<"{";
    for(auto it=a.begin(); it<a.end(); it++)
      __p(*it),cout<<",}\n"[it+1==a.end()]; 
  }
  template<typename T, typename ...Arg>
  void __p(T a1, Arg ...a) {
    __p(a1);
    __p(a...);
  }
  template<typename Arg1>
  void __f(const char *name, Arg1 &&arg1) {
    cout<<name<<" : ";
    __p(arg1);
    cout<<endl;
  }
  template<typename Arg1, typename ... Args>
  void __f(const char *names, Arg1 &&arg1, Args &&... args) {
    int bracket=0,i=0;
    for(;; i++)
      if(names[i]==','&&bracket==0)
        break;
      else if(names[i]=='(')
        bracket++;
      else if(names[i]==')')
        bracket--;
    const char *comma=names+i;
    cout.write(names,comma-names)<<" : ";
    __p(arg1);
    cout<<" | ";
    __f(comma+1,args...);
  }
  #define trace(...) cout<<"Line:"<<__LINE__<<"  ", __f(#__VA_ARGS__, __VA_ARGS__)
}


namespace FUN{
  void IO(string s = ""){
    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.precision(20); 
    cout << fixed;
    if(!s.empty()){
      freopen((s+".in").c_str(),"r",stdin);
      freopen((s+".out").c_str(),"w",stdout);
    }
  }

  const auto start_time = chrono::high_resolution_clock::now();
  void output_run_time(){
    // will work for ac,cc&&cf.
  #ifndef ONLINE_JUDGE
    auto end_time = chrono::high_resolution_clock::now();
    chrono::duration<double> diff = end_time-start_time;
      cout << "\n\n\nTime Taken : " << diff.count();
  #endif
  }

  template<class T> bool ckmin(T& a, const T b) { return b < a ? a = b, 1 : 0;}
  template<class T> bool ckmax(T& a, const T b) { return a < b ? a = b, 1 : 0;}
}


using namespace IN;
using namespace OUT;
using namespace FUN;



















template<class T> 
struct basic_segment_tree { 
  const T ID =  0;
  T comb(T a, T b){// comb(ID,b) = b
    return __gcd(a,b);
  }
  int n; vector<T> seg;
  void init(int _n){
    n = _n; seg.assign(2 * n,ID);
  }
  void pull(int p){
    seg[p] = comb(seg[2 * p], seg[2 * p + 1]);
  }
  void upd(int p, T val){ // update val at position p
    seg[p += n] = val;
    for(p /= 2; p; p /= 2) pull(p);
  }
  T query(int l, int r){ // query on interval [l, r]
    T ra = ID, rb = ID;
    for(l += n, r += n+1; l < r; l /= 2, r /= 2){
      if(l&1) ra = comb(ra,seg[l++]);
      if(r&1) rb = comb(seg[--r],rb);
    }
    return comb(ra,rb);
  }
};

template<typename T>
struct fenwick_tree{
  int tree_n = 0;
  T tree_sum = 0;
  vector<T> tree;
 
  fenwick_tree(int n = -1){
    if(n >= 0)
      init(n);
  }
 
  static int highest_bit(int x){
    return x == 0 ? -1 : 31 - __builtin_clz(x);
  }
 
  void init(int n) {
    tree_n = n;
    tree_sum = 0;
    tree.assign(tree_n + 1, 0);
  }
 
  // O(n) initialization of the Fenwick tree.
  template<typename T_array>
  void build(const T_array &initial){
    assert(int(initial.size()) == tree_n);
    tree_sum = 0;

    for(int i = 1; i <= tree_n; i++){
      tree[i] = initial[i-1];
      tree_sum += initial[i-1];
      for(int k = (i & -i) >> 1; k > 0; k >>= 1)
        tree[i] += tree[i - k];
    }
  }
 
  // index is in [0, tree_n).
  void update(int index, const T &change){
    assert(0 <= index && index < tree_n);
    tree_sum += change;

    for(int i = index + 1; i <= tree_n; i += i & -i)
      tree[i] += change;
  }
 
  // Returns the sum of the range [0, count).
  T query(int count) const {
    count = min(count, tree_n);
    T sum = 0;
    for(int i = count; i > 0; i -= i & -i)
      sum += tree[i];
    return sum;
  }
 
  // Returns the sum of the range [start, tree_n).
  T query_suffix(int start) const {
    return tree_sum - query(start);
  }
 
  // Returns the sum of the range [a, b).
  T query(int a, int b) const {
    return query(b) - query(a);
  }
 
  // Returns the element at index a in O(1) amortized across every index. Equivalent to query(a, a + 1).
  T get(int a) const {
    assert(0 <= a && a < tree_n);
    int above = a + 1;
    T sum = tree[above];
    above -= above & -above;
    while (a != above){
      sum -= tree[a];
      a -= a & -a;
    }
    return sum;
  }
 
  bool set(int index, T value){
    assert(0 <= index && index < tree_n);
    T current = get(index);

    if(current == value)
      return false;

    update(index, value - current);
    return true;
  }
 
  // Returns the largest p in `[0, tree_n]` such that `query(p) <= sum`. Returns -1 if no such p exists (`sum < 0`).
  // Can be used as an ordered set/multiset on indices in `[0, tree_n)` by using the tree as a 0/1 or frequency array:
  // `set(index, 1)` is equivalent to insert(index). `update(index, +1)` is equivalent to multiset.insert(index).
  // `set(index, 0)` or `update(index, -1)` are equivalent to erase(index).
  // `get(index)` provides whether index is present or not, or the count of index (if multiset).
  // `query(index)` provides the count of elements < index.
  // `find_last_prefix(k)` finds the k-th smallest element (0-indexed). Returns `tree_n` for `sum >= set.size()`.
  int find_last_prefix(T sum) const {
    if(sum < 0)
      return -1;

    int prefix = 0;

    for(int k = highest_bit(tree_n); k >= 0; k--)
      if(prefix + (1 << k) <= tree_n && tree[prefix + (1 << k)] <= sum){
        prefix += 1 << k;
        sum -= tree[prefix];
      }

    return prefix;
  }
};
 

signed main(){
  IO();

  int n;
  read(n);
  vector<int> a(n);
  read(a);

  basic_segment_tree<int> st;
  st.init(n);
  for(int i = 0; i < n; ++i)
    st.upd(i,a[i]);

  vector<int> ends(n,-1);
  for(int i = 0; i < n; ++i){
    int lo = i, hi = n;
    while(hi - lo > 1){
      int mid = (hi + lo)/2;
      st.query(i,mid) - (mid - i + 1) >= 0 ? lo = mid : hi = mid;
    }
    if(st.query(i,lo) == (lo - i + 1))
      ends[lo] = i;
  }


  fenwick_tree<int> ft;
  ft.init(n);

  int ans = 0;
  for(int i = 0; i < n; ++i){
    if(ends[i] >= 0 && ft.query(ends[i],i) == 0){
      ++ans;
      ft.update(i,1);
    }
    cout << ans << " ";
  }



  output_run_time();
  return 0;
}
















 

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define ld long double
#define pll pair<long long, long long>
#define vll vector<long long>
#define vvll vector<vector<long long>>
#define vpll vector<pair<long long, long long>>
#define vec vector
#define indexed_set                                          \
    tree<long long, null_type, less<long long>, rb_tree_tag, \
         tree_order_statistics_node_update>

#define FOR(i, s, e) for (long long i = s; i < e; i++)
#define CFOR(i, s, e) for (long long i = s; i <= e; i++)
#define RFOR(i, e, s) for (long long i = e - 1; i >= s; i--)
#define TRAV(a, c) for (auto a : c)
#define ITER(it, cs, ce) for (auto it = cs; it != ce; it++)
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << "ln" << __LINE__ << ": " << #x << " = " << x << endl
mt19937_64 rng(100);

template <class T>
string to_string(vector<T> &vec) {
    std::ostringstream vts;
    if (!vec.empty()) {
        std::copy(vec.begin(), vec.end() - 1,
                  std::ostream_iterator<T>(vts, ", "));
        vts << vec.back();
    }
    return "[" + vts.str() + "]";
}

#define MOD 1000000007

#define FASTIO ;
#define PRECISION ;
//#define FILE ;

#define SINGLE ;
//#define MULTIPLE ;
//#define GOOGLE ;

ll gcd(ll a, ll b) { return ((b == 0) ? a : gcd(b, a % b)); }

struct sparse_table {
    vector<vector<ll>> table;

    sparse_table(vector<ll> a) {
        ll n = a.size() + 1;
        ll h = ceil(log2(n));
        table = vector<vector<ll>>(h, vector<ll>(n));
        for (ll i = 0; i < n; i++) table[0][i] = a[i];
        for (ll i = 1; i < h; i++) {
            for (ll j = 0; j + (1 << i) <= n; j++) {
                table[i][j] =
                    gcd(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    ll query(ll l, ll r) {
        r++;
        ll p = 31 - __builtin_clz(r - l);
        return gcd(table[p][l], table[p][r - (1 << p)]);
    }
};

void solve() {
    ll n;
    cin >> n;
    vll a(n);
    FOR(i, 0, n) cin >> a[i];
    sparse_table st(a);
    ll l = 0;
    ll curr = 0;
    FOR(r, 0, n) {
        while (st.query(l, r) < r - l + 1) l++;
        if (st.query(l, r) == r - l + 1) {
            curr++;
            l = r + 1;
        }
        cout << curr << " ";
    }
    cout << "\n";
}

int main() {
#ifdef FASTIO
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#endif
#ifdef PRECISION
    cout << fixed << setprecision(10);
#endif
#ifdef FILE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
#ifdef SINGLE
    solve();
#endif
#ifdef MULTIPLE
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        solve();
    }
#endif
#ifdef GOOGLE
    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cout << "Case #" << i << ": ";
        solve();
    }
#endif
}

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<random>
#include<chrono>
#include<deque>
#include<cassert>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<vector>
#define fi first
#define se second
#define pb push_back
#define mp std::make_pair
#define ulf Useful_little_function
#define abs ccf
#define inline __attribute__((always_inline))inline
#define INF (0x3f3f3f3f)
#define INT_INF (2147483647)
#define LLINF (0x3f3f3f3f3f3f3f3fll)
#define LL_INF (9223372036854775807)
#define memset __builtin_memset
#define popcount __builtin_popcount
std::mt19937 rnd(std::chrono::system_clock::now().time_since_epoch().count());
typedef long long ll;
typedef std::pair<int,int> pii;
typedef unsigned int uint;
typedef unsigned long long ull;
inline void file(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
namespace IO{
    #define BUF_SIZE (1<<16)
    #define OUT_SIZE (1<<16)
    bool IOerror=0;
    inline char nc(){static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;if(p1==pend){p1=buf;pend=buf+fread(buf,1,BUF_SIZE,stdin);if(pend==p1)return IOerror=1,-1;}return *p1++;}
    inline bool blank(char ch){return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';}
    inline void read(int &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
    inline void read(ll &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(sign)x=-x;}
    inline void read(double &x){bool sign=0;char ch=nc();x=0;for(;blank(ch);ch=nc());if(IOerror)return;if(ch=='-')sign=1,ch=nc();for(;ch>='0'&&ch<='9';ch=nc())x=x*10+ch-'0';if(ch=='.'){double tmp=1;ch=nc();for(;ch>='0'&&ch<='9';ch=nc())tmp/=10.0,x+=tmp*(ch-'0');}if(sign)x=-x;}
    inline void read(char *s){char ch=nc();for(;blank(ch);ch=nc());if(IOerror)return;for(;!blank(ch)&&!IOerror;ch=nc())*s++=ch;*s=0;}
    inline void read(char &c){for(c=nc();blank(c);c=nc());if(IOerror){c=-1;return;}}
    struct Ostream_fwrite{
        char *buf,*p1,*pend;
        Ostream_fwrite(){buf=new char[BUF_SIZE];p1=buf;pend=buf+BUF_SIZE;}
        inline void out(char ch){if(p1==pend){fwrite(buf,1,BUF_SIZE,stdout);p1=buf;}*p1++=ch;}
        inline void print(int x){static char s[15],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void println(int x){print(x);out('\n');}
        inline void print(ll x){static char s[25],*s1;s1=s;if(!x)*s1++='0';if(x<0)out('-'),x=-x;while(x)*s1++=x%10+'0',x/=10;while(s1--!=s)out(*s1);}
        inline void println(ll x){print(x);out('\n');}
        inline void print(double x,int y){//y<18
			static ll mul[]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000LL,100000000000LL,1000000000000LL,10000000000000LL,100000000000000LL,1000000000000000LL,10000000000000000LL,100000000000000000LL};
            if(x<-1e-12)out('-'),x=-x;x*=mul[y];ll x1=(ll)floor(x);if(x-floor(x)>=0.5)++x1;ll x2=x1/mul[y],x3=x1-x2*mul[y];print(x2);if(y>0){out('.');for(size_t i=1;i<y&&x3*mul[i]<mul[y];out('0'),++i);print(x3);}
        }
        inline void println(double x,int y){print(x,y);out('\n');}
        inline void print(char *s){while(*s)out(*s++);}
        inline void println(char *s){while(*s)out(*s++);out('\n');}
        inline void flush(){if(p1!=buf){fwrite(buf,1,p1-buf,stdout);p1=buf;}}
        ~Ostream_fwrite(){flush();}
    }Ostream;
    inline void print(int x){Ostream.print(x);}
    inline void println(int x){Ostream.println(x);}
    inline void print(char x){Ostream.out(x);}
    inline void println(char x){Ostream.out(x);Ostream.out('\n');}
    inline void print(ll x){Ostream.print(x);}
    inline void println(ll x){Ostream.println(x);}
    inline void print(double x,int y){Ostream.print(x,y);}
    inline void println(double x,int y){Ostream.println(x,y);}
    inline void print(char *s){Ostream.print(s);}
    inline void println(char *s){Ostream.println(s);}
    inline void println(){Ostream.out('\n');}
    inline void flush(){Ostream.flush();}
    #undef OUT_SIZE
    #undef BUF_SIZE
}using namespace IO;
namespace Little_function{
	inline int abs(int x){return x<0?-x:x;}
	inline ll abs(ll x){return x<0?-x:x;}
	inline double abs(double x){return x<0?-x:x;}
	inline int max(const int &a,const int &b){return a>b?a:b;}
	inline ll max(const ll &a,const ll &b){return a>b?a:b;}
	inline double max(const double &a,const double &b){return a>b?a:b;}
	inline int min(const int &a,const int &b){return a<b?a:b;}
	inline ll min(const ll &a,const ll &b){return a<b?a:b;}
	inline double min(const double &a,const double &b){return a<b?a:b;}
	inline void swap(int &x,int &y){x^=y^=x^=y;}
	inline void swap(ll &x,ll &y){x^=y^=x^=y;}
	inline void swap(double &x,double &y){double t=x;x=y,y=t;}
	inline int madd(const int &a,const int &b,const int &p){return (a+b)%p;}
	inline int mdel(const int &a,const int &b,const int &p){return (a-b<0?a-b+p:a-b);}
	int gcd(int a,int b){return !b?a:gcd(b,a%b);}
	ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
}using namespace Little_function;
const int N=2e5+13;
struct Node{int val,l,r,nxt;}a[N];
int n,head,tot;
int main(){
	read(n);int sum=0;
	for(int i=1;i<=n;++i){
		int x;read(x);
		a[++tot]=(Node){x,i,i,head};head=tot;
		for(int j=head;j;j=a[j].nxt) a[j].val=gcd(a[j].val,x);
		for(int j=head;j&&a[j].nxt;j=a[j].nxt)
			if(a[j].val==a[a[j].nxt].val) a[j].l=a[a[j].nxt].l,a[j].nxt=a[a[j].nxt].nxt;
		for(int j=head,c=0;j;c+=a[j].r-a[j].l+1,j=a[j].nxt)
			if(a[j].val>=c+1&&a[j].val<=c+a[j].r-a[j].l+1){++sum;head=0;break;}
		print(sum),print(' ');
	}
	return 0;
}

#define A45 cout << ans << " ";
#define A44 __gcd(f[l][zz],
#define A43 f[500005][25];
#define A42 __gcd(f[j][i
#define A41 (func(best,
#define A40 (func(mid,
#define A3F a[500005],
#define A3E main(void)
#define A3D namespace
#define A3C 1][zz]);
#define A3B func(int
#define A3A f[j][i]
#define A39 f[i][0]
#define A38 ans++;
#define A37 __lg(r
#define A36 1))][i
#define A35 return
#define A34 a[i];
#define A33 using
#define A32 while
#define A31 ++j)
#define A30 last
#define A2F (int
#define A2E mid;
#define A2D ++i)
#define A2C best
#define A2B std;
#define A2A else
#define A29 1]);
#define A28 int
#define A27 20;
#define A26 1],
#define A25 mid
#define A24 ans
#define A23 f[j
#define A22 1);
#define A21 f[r
#define A20 for
#define A1F cin
#define A1E zz)
#define A1D 1)
#define A1C i)
#define A1B i,
#define A1A if
#define A19 1,
#define A18 l,
#define A17 l;
#define A16 1;
#define A15 <<
#define A14 <=
#define A13 ==
#define A12 n;
#define A11 >>
#define A10 r)
#define AF (1
#define AE (i
#define AD (l
#define AC 0,
#define AB zz
#define AA 0;
#define A9 r
#define A8 1
#define A7 -
#define A6 +
#define A5 =
#define A4 j
#define A3 l
#define A2 i
#define A1 {
#define A0 }
#include <bits/stdc++.h>
#define A46 A33 A3D A2B A28 A3F A43 A28 A3B A18 A28
#define A47 A10 A1 A28 AB A5 A37 A7 A3 A6 A22
#define A48 A35 A44 A21 A7 AF A15 A1E A6 A3C A0
#define A49 A28 A3E A1 A28 A12 A1F A11 A12 A20 A2F
#define A4A A2 A5 A16 A2 A14 A12 A2D A1 A1F A11
#define A4B A34 A0 A20 A2F A2 A5 A16 A2 A14 A12
#define A4C A2D A1 A39 A5 A34 A0 A20 A2F A2 A5
#define A4D A16 A2 A14 A27 A2D A1 A20 A2F A4 A5
#define A4E A16 A4 A6 AF A15 A1C A7 A8 A14 A12
#define A4F A31 A1 A3A A5 A42 A7 A26 A23 A6 AF
#define A50 A15 AE A7 A36 A7 A29 A0 A0 A28 A30
#define A51 A5 AC A24 A5 AA A20 A2F A2 A5 A16
#define A52 A2 A14 A12 A2D A1 A28 A3 A5 A30 A6
#define A53 A19 A9 A5 A1B A2C A5 A17 A32 AD A14
#define A54 A10 A1 A28 A25 A5 AD A6 A10 A11 A16
#define A55 A1A A40 A1C A14 A2 A7 A25 A6 A1D A1
#define A56 A3 A5 A25 A6 A19 A2C A5 A2E A0 A2A
#define A57 A1 A9 A5 A25 A7 A16 A0 A0 A1A A41
#define A58 A1C A13 A2 A7 A2C A6 A1D A1 A30 A5
#define A59 A1B A38 A0 A45 A0 A0 
#define A5A A46 A47 A48 A49 A4A A4B A4C A4D A4E A4F
#define A5B A50 A51 A52 A53 A54 A55 A56 A57 A58 A59
#define A5C A5A A5B 
#define A5D(__FOX__) __FOX__
A5D(A5C)

#include<bits/stdc++.h>
using namespace std;
#define Jay_JAGANATH ios_base::sync_with_stdio(false); cin.tie(NULL)
#define ll long long 
#define lld long long double
#define sz(a) int((a).size())
#define endl '\n' 
#define all(x) (x).begin(), (x).end()
#define pb push_back 
#define ppb pop_back
#define mp make_pair 
#define ff first   
#define ss second
#define INF 1e18   
ll mod = 1e9+7;
ll MOD = 998244353;


template < typename T >
struct SparseTable {
    vector<vector<T>> table;
    vector<int> log;
    int maxLog;
    SparseTable(int n, vector<T> &arr) {
        log.resize(n+1);
        log[1] = 0;
        for(int i=2;i<=n;i++) {
            log[i] = 1 + log[i/2];
        }
        maxLog = log[n];
        build(arr);
    }
    T combine(T &x, T &y) {
        return __gcd(x, y);
    }
    void build(vector<T> &arr) {
        int n = arr.size();
        table.assign(n, vector<T>(25));
        for(int l=n-1;l>=0;l--) {
            for(int w=0;w<25;w++) {
                int r = l + (1 << w) - 1;
                if(r >= n) break;
                if(w == 0) table[l][w] = arr[l];
                else table[l][w] = combine(table[l][w-1], table[l + (1 << (w-1))][w-1]); 
            }
        }
    }
    int queryIdempotent(int l, int r) {
        int w = r - l;
        int power = log[w];
        return combine(table[l][power] , table[r - (1 << power)+1][power]);
    }
    
};

void solve() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0;i<n;i++) {
        cin >> arr[i];
    }
    SparseTable<int> sp(n, arr);
    set<int> s;
    int ans = 0;
    for(int i=0;i<n;i++) {
        if(arr[i] == 1) {
            ans++;
            s.insert(i);
            cout << ans << " ";
            continue;
        }
        int l = 0, r = i;
        bool f = 0;
        int ind = -1; 
        while(l <= r) {
            int mid = (l + r) / 2;
            int len = i - mid + 1;
            int gcd = sp.queryIdempotent(mid, i);
            if( gcd == len) {
                f = 1;
                ind = mid;
                break;
            }
            if(gcd < len) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        if(f) {
            auto it = s.lower_bound(ind);
            if(it == s.end()) {
                ans++;
                s.insert(i);
            }
        }
        cout << ans << " ";
    }
    cout << endl;
}
 
int32_t main() {
    Jay_JAGANATH;   
    cout.tie(NULL);
    int t=1;
    // cin >> t;
    while(t--) {
        solve();
    }
    #ifndef ONLINE_JUDGE
        cerr << "\nTime: " << (float)clock() / CLOCKS_PER_SEC * 1000 << " ms" << endl;
    #endif
} 
/*
 
*/

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Size(a) (int)a.size()
#define ll long long
#define ld long double

// #define int long long

using namespace std;

const int N = 2e5 + 100;

int n;
int a[N];
int t[N * 4];

void build() {
    for (int i = 0; i < n; i++)
        t[i + n] = a[i];
    for (int i = n - 1; i >= 1; i--)
        t[i] = gcd(t[i << 1], t[(i << 1) | 1]);
}

int get(int l, int r) {
    l += n;
    r += n;
    int res = 0;
    while (l < r) {
        if (l & 1) {
            res = gcd(res, t[l]);
            l++;
        }
        if (r & 1) {
            r ^= 1;
            res = gcd(res, t[r]);
        }
        l >>= 1;
        r >>= 1;
    }
    return res;
}

void update(int i, int x) {
    a[i] = x;
    i += n;
    t[i] = x;
    i >>= 1;
    while (i) {
        t[i] = gcd(t[i << 1], t[(i << 1) | 1]);
        i >>= 1;
    }
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    build();

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int x = a[i]; 
        int last = 1e9;
        while (true) {
            int l = -1, r = i;
            while (l + 1 != r) {
                int m = (l + r) / 2;
                if (get(m, i + 1) >= x)
                    r = m;
                else
                    l = m;
            }
            if (i - last + 1 < x && x <= i - r + 1) {
                ans++;
                update(i, 1);
                break;
            }
            last = r;
            if (r == 0)
                break;
            x = gcd(x, a[r - 1]);
        }
        cout << ans << " ";
    }
    cout << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    #ifdef DIMSS
        freopen("test.txt", "r", stdin);
    #endif

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
        #ifdef DIMSS
            cerr << "--------\n";
        #endif
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long

int t, n, m, k, a[1000005], mod = 1e9 + 7, Gcd[200005][20], ans[1000005], L[200005];
string s;
mt19937_64 rng;

int mul(int x, int y){
    if(y == 0) return 1;
    int ans = mul(x, y / 2);
    if(y % 2 == 0) return (ans * ans) % mod;
    else return (((ans * ans) % mod) * x) % mod;
}

int getgcd(int l, int r){
    int p = L[r - l + 1]; 
    return __gcd(Gcd[l][p], Gcd[r - (1 << p) + 1][p]);
}

void solve(){
    for(int i = 2; i <= 2e5; i++) L[i] = L[i / 2] + 1;
    for(int i = 1; i <= n; i++) Gcd[i][0] = a[i];
    for(int i = 1; i <= 20; i++){
        for(int j = 1; j + (1 << i - 1) <= n; j++){
            Gcd[j][i] = __gcd(Gcd[j][i - 1], Gcd[j + (1 << i - 1)][i - 1]);
        }
    }
    for(int i = 1; i <= n; i++){
        int l = i, r = n + 1;
        while(r - l > 1){
            int mid = (l + r) / 2;
            if(getgcd(i, mid) >= mid - i + 1) l = mid;
            else r = mid;
        }
        if(getgcd(i, l) == l - i + 1){
            ans[l]++, ans[n + 1]--;
            i = l;
        }
    } 
    for(int i = 1; i <= n; i++) ans[i] += ans[i - 1];
    for(int i = 1; i <= n; i++) cout << ans[i] <<" ";
}

signed main(){
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
    rng.seed((int)main ^ time(0));
    #ifdef Kawaii
        auto starttime = chrono::high_resolution_clock::now();
    #endif

    cin >> n; 
    for(int i = 1; i <= n; i++){
        cin >> a[i]; 
    }
    solve();

    #ifdef Kawaii
        auto endtime = chrono::high_resolution_clock::now();
        auto duration = chrono::duration_cast<chrono::milliseconds>(endtime - starttime).count(); 
        cout << "\n=====" << "\nUsed: " << duration << " ms\n";
    #endif
}

#include<bits/stdc++.h>
#define lp long long
#define ulp unsigned long long
#define pa pair < lp , lp >
#define fi first
#define se second
#define mp make_pair
#define ls x<<1
#define rs x<<1|1
#define kp push_back
#define db double
#define itn insert
#define pc putchar
#define rep(i,x,y) for(lp i=(x);i<=(y);i++)
#define per(i,x,y) for(lp i=(x);i>=(y);i--)
using namespace std;

inline lp read(){
    lp r=0,f=0;char c=getchar();
    while(!isdigit(c))f=c=='-',c=getchar();
    while(isdigit(c))r=r*10+(c^48),c=getchar();
    return f?-r:r;
}

inline lp minn(lp a,lp b){return a<b?a:b;}
inline lp maxx(lp a,lp b){return a>b?a:b;}

//inline lp sqt(lp x){lp res=sqrt(x)+1;while(res*res>x)res--;return res;}

lp gcd(lp a,lp b){return !b?a:gcd(b,a%b);}
lp lcm(lp a,lp b){return a/gcd(a,b)*b;}

void wr(lp x){if(x<0)x=-x,pc('-');if(x>9)wr(x/10);pc(x%10+'0');}

const lp ml=1e6+101;
const lp inf=1e15;
//const lp mk=+101;
//const lp mo=1e9+7;
//const lp mo=998244353;

lp t,n,m,q;
lp ans;

lp x[ml],ins[ml];
//pa a[ml];
//char s[ml];
//string s;
//vector < lp > e[ml];
//map < lp , lp > atl;
//multiset < lp > s;





//---------------------------------------------------------------------------------------------------
//lp qpow(lp x,lp y=mo-2){lp res=1;while(y){if(y&1)res=res*x%mo;x=x*x%mo;y>>=1;}return res;}

/*
lp fac[ml],inv[ml];

void init_C(lp l){
    fac[0]=inv[0]=1;
    for(lp i=1;i<=l;i++)fac[i]=fac[i-1]*i%mo;
    inv[l]=qpow(fac[l]);
    for(lp i=l-1;i>=1;i--)inv[i]=inv[i+1]*(i+1)%mo;
}

lp C(lp a,lp b){
	if(a<0||b<0||a<b)return 0;
	return fac[a]*inv[b]%mo*inv[a-b]%mo;
}
*/
//---------------------------------------------------------------------------------------------------




//---------------------------------------------------------------------------------------------------
/*
struct BIT{
    lp sz[ml];

    lp query(lp x){lp res=0;for(;x>=1;x-=x&-x)res+=sz[x];return res;}

    void modify(lp x,lp y=1){for(;x<=n;x+=x&-x)sz[x]+=y;}
}str;
*/
//----------------------------------------------------------------------------------------------------






//----------------------------------------------------------------------------------------------------
/*
-----------------------------------------------------------------------------------
鍔ㄦ€佸紑鐐?鍖洪棿淇敼&鏈€灏忓€?灏佽 鏉庤秴绾挎鏍?

auther:wuxingzhi

浣跨敤鍓嶏細init(鍊煎煙)锛屾敼ML	

鍑芥暟锛歁odify,Query,init

Ps:姹傛渶澶у€肩洿鎺ユ妸涓変釜">"鏀规垚"<"锛屾妸鈥渞eturn inf"鏀规垚"return -inf"锛屾妸"minn"鏀规垚"maxx"
-----------------------------------------------------------------------------------
*/
/*
struct Lc{
#define lo lson[x]
#define ro rson[x]

	static const lp ML=1e6+101;
	const lp inf=1e15;
	
	lp N,tot;
	
	lp lson[ML<<2],rson[ML<<2],k[ML<<2],b[ML<<2],vis[ML<<2];
	
	lp calc(lp x,lp k,lp b){return x*k+b;}
	
	void init(lp Num){N=Num;for(lp i=1;i<=tot;i++)lson[i]=rson[i]=k[i]=b[i]=vis[i]=0;tot=1;}
	
	lp modify(lp qk,lp qb,lp ql,lp qr,lp x,lp l,lp r){
		if(!x)x=++tot;
		lp mid=(l+r)>>1;
		if(ql<=l&&qr>=r){
			if(!vis[x]){vis[x]=1,k[x]=qk,b[x]=qb;return x;}
			if(calc(mid,k[x],b[x])>calc(mid,qk,qb))swap(qk,k[x]),swap(qb,b[x]);
			if(calc(l,k[x],b[x])>calc(l,qk,qb))lo=modify(qk,qb,ql,qr,lo,l,mid);
			if(calc(r,k[x],b[x])>calc(r,qk,qb))ro=modify(qk,qb,ql,qr,ro,mid+1,r);
			return x;
		}
		if(ql<=mid)lo=modify(qk,qb,ql,qr,lo,l,mid);
		if(qr>mid)ro=modify(qk,qb,ql,qr,ro,mid+1,r);
		return x;
	}
	
	lp query(lp d,lp x,lp l,lp r){
		if(!vis[x]||!x)return inf;
		lp res=calc(d,k[x],b[x]),mid=(l+r)>>1;
		if(l==r)return res;
		if(d<=mid)return minn(res,query(d,lo,l,mid));
		else return minn(res,query(d,ro,mid+1,r));
	}
	
	void Modify(lp k,lp b,lp l=-1,lp r=-1){l==-1?modify(k,b,0,N,1,0,N):modify(k,b,l,r,1,0,N);}
	
	lp Query(lp d){return query(d,1,0,N);}
	
#undef lo
#undef ro
}t;
*/
//-----------------------------------------------------------------------------------------------------------

const lp mk=22;
const lp L=21;

lp s[ml][mk];

lp get(lp l,lp r){
	lp b=__lg(r-l+1);
	return gcd(s[l][b],s[r-(1ll<<b)+1][b]);
}

void init(){
	for(lp i=1;i<=n;i++)s[i][0]=x[i];
	for(lp i=1;i<=L;i++)
	for(lp j=1;j<=n-(1ll<<i)+1;j++)s[j][i]=gcd(s[j][i-1],s[j+(1ll<<(i-1))][i-1]);
}

int main(){
	cin>>n;
	for(lp i=1;i<=n;i++)x[i]=read();
	init();
	lp lst=0;
	for(lp i=1;i<=n;i++){
		lp l=lst+1,r=i,mid,res=-1;
		while(l<=r){
			mid=(l+r)>>1;
			if(get(mid,i)-(i-mid+1)>=0)r=mid-1,res=mid;
			else l=mid+1;
		}
		//cout<<endl<<" step inf "<<lst<<" "<<i<<" "<<res<<endl;
		if((res==-1)||(get(res,i)!=i-res+1))cout<<ans<<" ";
		else lst=i,ans++,cout<<ans<<" ";
	}
return 0;
}