#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define F1(x,y,z) for(int x=y;xz;x--) #define F4(x,y,z) for(int x=y;x>=z;x--) #define pb push_back #define LL long long #define co complex #define MAX 100005 #define AMAX 1500 #define MOD 1000000007 #define f(c,d) ((1<<(c))*(d)) using namespace std; struct w{ int cnt,x[2]; } ww; int t,n,ta,tb,y[MAX],ans[MAX]; vector x; int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); x.clear(); x.pb(ww); F2(a,1,n){ ta=0; F4(b,30,0){ tb=(a&(1<y[a]){ ta=x[ta].x[1]; ans[a]+=1<