#include "Annalib.h"
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "ftree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r)
{
return uniform_int_distribution<int>(l,r)(rd);
}
void phongbeo();
const int inf = 1e8;
const ll mod2 = 1e9+7;
const ll base=67;
int n, m, s1, s2, s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int i, s10, s12,k1,k2,k3,s11,lim,w,l,r ;
int kk;
int el = 19;
bool check[151];
bool use[151];
vector<int> per;
bool can(int x,int y)
{
if(y==0)return (check[per[x]]&check[per[x+1]]);
else if(y==1) return check[per[x]];
else return check[per[x+1]];
}
void go(int x,int y)
{
if(y==0)
{
// Set(x,1);
// Set(x+1,1);
use[per[x]]=1;
use[per[x+1]]=1;
}
else if(y==1)
{
// Set(x,1);
use[per[x]]=1;
}
else
{
// Set(x+1,1);
use[per[x+1]]=1;
}
}
void Anna( int N, long long x, int k, int P[] )
{
n=N;
per.resize(n);
iota(per.begin(),per.end(),0);
shuffle(per.begin(),per.end(),mt19937_64(1472008));
memset(check,1,sizeof check);
memset(use,0,sizeof use);
for(int i=1; i<=k; i++)
check[P[i-1]]=0;
vector<int> v;
while(x!=0)
{
v.pb(x%3);
x/=3;
}
reverse(v.begin(),v.end());
l=0;
for(int i=0; i<n-1; i+=2)
{
if(l==v.size()) break;
if(can(i,v[l]))
{
go(i,v[l]);
l++;
}
}
for(int i=0; i<n; i++)
Set(i,use[i]);
}/*
void phongbeo()
{
Anna(150,13435,0,a);
cout<<Bruno(150,a);
}*/
#include "Brunolib.h"
#include<bits/stdc++.h>
using namespace std;
long long Bruno( int n, int a[] ){
vector<int> per;
per.resize(n);
iota(per.begin(),per.end(),0);
shuffle(per.begin(),per.end(),mt19937_64(1472008));
long long s=0;
for(int i=0;i<n-1;i+=2)
if(a[per[i]]||a[per[i+1]])
{
s=s*3;
if(a[per[i]]&&a[per[i+1]])s;
else if(a[per[i]])s+=1;
else s+=2;
}
return s;
}
