#include "Ali.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt13937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
namespace
{
vi opt_list = {13,12,12,12,11,12,12,11,11,12,11,12,11,11,11,10,11,11,10,10,11,10,12,11,11,11,10,11,11,10,10,11,10,12,11,11,11,10,11,11,10,10,11,10,11,10,10,10,9,10,10,9,9,10,9,12,11,11,11,10,11,11,10,10,11,10,12,11,11,11,10,11,11,10,10,11,10,11,10,10,10,9,10,10,9,9,10,9,11,10,10,10,9,10,10,9,9,10,9,12,11,11,11,10,11,11,10,10,11,10,11,10,10,10,9,10,10,9,9,10,9};
vector<vi> dists_sets = {
{1,2,2,2,2,2,2},
{1,2,2,2,2,3,1},
{1,2,2,2,2,4,0},
{1,2,2,2,3,2,1},
{1,2,2,2,3,3,0},
{1,2,2,2,4,2,0},
{1,2,2,3,2,2,1},
{1,2,2,3,2,3,0},
{1,2,2,3,3,1,1},
{1,2,2,3,3,2,0},
{1,2,2,3,4,1,0},
{1,2,2,4,2,2,0},
{1,2,2,4,3,1,0},
{1,2,2,4,4,0,0},
{1,2,3,2,2,2,1},
{1,2,3,2,2,3,0},
{1,2,3,2,3,1,1},
{1,2,3,2,3,2,0},
{1,2,3,2,4,1,0},
{1,2,3,3,2,1,1},
{1,2,3,3,2,2,0},
{1,2,3,3,3,1,0},
{1,2,3,3,4,0,0},
{1,2,3,4,1,1,1},
{1,2,3,4,1,2,0},
{1,2,3,4,2,1,0},
{1,2,3,4,3,0,0},
{1,2,3,5,1,1,0},
{1,2,3,5,2,0,0},
{1,2,4,2,2,2,0},
{1,2,4,2,3,1,0},
{1,2,4,2,4,0,0},
{1,2,4,3,2,1,0},
{1,2,4,3,3,0,0},
{1,2,4,4,1,1,0},
{1,2,4,4,2,0,0},
{1,2,4,5,1,0,0},
{1,2,4,6,0,0,0},
};
vector<string> trees[16];
map<string,int> tree_map;
void gen_trees()
{
rep2(i,0,13) trees[i] = {};
trees[0].pb("");
rep2(i,1,13)
{
rep2(k,0,i)
{
if(k > i-1-k || k >= 7 || i-1-k >= 7) continue;
forall(it,trees[k])
{
forall(it2,trees[i-1-k])
{
if(it < it2) trees[i].pb("("+it+it2+")");
else trees[i].pb("("+it2+it+")");
}
}
}
}
rep(i,siz(trees[13])) tree_map[trees[13][i]] = i;
}
vi graph[130001];
vi graph2[130001];
bool is_in[130001];
vector<vi> comps;
map<int,int> vert_ind;
int comp_tree[100001];
int n;
vi dfs_comps(int v, int pop)
{
vi cur = {v};
forall(it,graph[v])
{
if(it != pop)
{
vi v2 = dfs_comps(it,v);
forall(it2,v2) cur.pb(it2);
}
}
if(siz(cur) >= 7)
{
comps.pb(cur);
cur = {};
}
return cur;
}
int dfs_sub(int v, int pop)
{
int s = 1;
forall(it,graph2[v]) if(it != pop) s += dfs_sub(it,v);
return s;
}
string sub_hash[100001];
string hash_tree(int v, int pop)
{
vi p;
forall(it,graph2[v]) if(it != pop) p.pb(it);
string ans;
if(siz(p) == 0) ans = "()";
else if(siz(p) == 1) ans = "("+hash_tree(p[0],v)+")";
else
{
string s1 = hash_tree(p[0],v);
string s2 = hash_tree(p[1],v);
if(s2 < s1)
{
swap(s1,s2);
swap(p[0],p[1]);
}
ans = "("+s1+s2+")";
}
graph2[v] = p;
sub_hash[v] = ans;
return ans;
}
int cur_ind;
vector<vi> comps_d;
void bfs_inds(int v)
{
vi cur = {v};
vi d(7,0);
int d2 = 0;
while(siz(cur) != 0)
{
d[d2++] = siz(cur);
forall(it,cur) vert_ind[it] = cur_ind++;
vi cur2;
forall(it,cur)
{
vector<pair<string,int>> add;
forall(it2,graph2[it])
{
if(it2 != it) add.pb({sub_hash[it2],it2});
}
sort(all(add));
forall(it,add) cur2.pb(it.ss);
}
cur = cur2;
}
comps_d.pb(d);
}
void set_inds(vi x, int c)
{
forall(it,x) is_in[it] = 1;
forall(it,x)
{
graph2[it] = {};
forall(it2,graph[it]) if(is_in[it2]) graph2[it].pb(it2);
}
int r = x[0];
int cur = n;
rep2(i,n,n+20) graph2[i] = {};
while(siz(x) < 13)
{
int pop = r;
int r2 = r;
while(true)
{
int nxt = -1;
forall(it,graph2[r2])
{
if(it != pop && dfs_sub(it,r2) < 6) nxt = it;
}
if(nxt == -1)
{
graph2[r2].pb(cur);
x.pb(cur);
cur++;
break;
}
else
{
pop = r2;
r2 = nxt;
}
}
}
string h = hash_tree(r,r);
comp_tree[c] = tree_map[h];
cur_ind = c*13;
bfs_inds(r);
forall(it,x) is_in[it] = 0;
}
int dist[100001];
void bfs(int v)
{
rep(i,n) dist[i] = 1e9;
queue<pii> q;
q.push({v,0});
while(!q.empty())
{
pii t = q.front();
q.pop();
if(dist[t.ff] != 1e9) continue;
dist[t.ff] = t.ss;
forall(it,graph[t.ff]) q.push({it,t.ss+1});
}
}
const int k = 1447;
pii pair_[k*k+1];
bool was = 0;
void init2()
{
if(!was)
{
was = 1;
int cur = 0;
rep2(i,0,k-1)
{
rep2(j,i,k-1)
{
pair_[cur++] = {i,j};
}
}
}
}
pll segs[32];
int comp_ind[100003];
}
void Init(int N, vi U, vi V)
{
n = N;
rep(i,n) graph[i] = {};
comps_d = {};
gen_trees();
rep(i,n-1)
{
graph[U[i]].pb(V[i]);
graph[V[i]].pb(U[i]);
}
comps = {};
int r = 0;
rep(i,n) if(siz(graph[i]) == 1)
{
r = i;
break;
}
vi x = dfs_comps(r,r);
if(siz(x) != 0) comps.pb(x);
int c = 0;
forall(it,comps) set_inds(it,c++);
rep(i,siz(comps)) forall(it,comps[i]) comp_ind[it] = i;
rep(i,n) SetID(i,vert_ind[i]);
}
string SendA(string S)
{
ll l = 0;
ll r = 1;
rep2(i,1,31)
{
if(i == 7) continue;
segs[i] = {l,r};
ll len = (r-l+1)*(i != 8 ? 2 : 4);
l = r+1;
r = l+len-1;
}
int x = 0;
int y = 0;
int ans3 = 0;
rep(i,20) if(S[i] == '1') ans3 += (1<<i);
init2();
x = pair_[ans3].ff;
y = pair_[ans3].ss;
if(x == y)
{
string ans;
rep(i,7)
{
if(comp_tree[x]&(1<<i)) ans += "1";
else ans += "0";
}
return ans;
}
bfs(comps[x][0]);
vi d = comps_d[x];
int ind = 0;
rep(i,siz(dists_sets)) if(d == dists_sets[i]) ind = i;
pii best = {1e9,1e9};
forall(it,comps[y]) best = min(best,{dist[it],it});
ll comb = 0;
rep(i,comp_tree[y]) comb += opt_list[i];
int opt = (vert_ind[best.ss]%13);
vi opts;
set<int> bad;
forall(it,comps[y])
{
int c = 0;
forall(it2,graph[it]) if(comp_ind[it2] == comp_ind[it]) c++;
if(c == 3) bad.insert(vert_ind[it]%13);
}
rep(i,13) if(bad.find(i) == bad.end()) opts.pb(i);
forall(it,opts)
{
if(it == opt) break;
comb++;
}
ll ans = ind+best.ff*(ll)siz(dists_sets)+comb*(ll)siz(dists_sets)*(ll)(n-1);
string ans2;
rep2(i,1,31)
{
if(i == 7) continue;
if(segs[i].ff <= ans && ans <= segs[i].ss)
{
rep(j,i)
{
if((ans-segs[i].ff)&(1LL<<(ll)j)) ans2 += "1"; else ans2 += "0";
}
}
}
return ans2;
}
#include "Benjamin.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt13937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
namespace
{
vi opt_list = {13,12,12,12,11,12,12,11,11,12,11,12,11,11,11,10,11,11,10,10,11,10,12,11,11,11,10,11,11,10,10,11,10,12,11,11,11,10,11,11,10,10,11,10,11,10,10,10,9,10,10,9,9,10,9,12,11,11,11,10,11,11,10,10,11,10,12,11,11,11,10,11,11,10,10,11,10,11,10,10,10,9,10,10,9,9,10,9,11,10,10,10,9,10,10,9,9,10,9,12,11,11,11,10,11,11,10,10,11,10,11,10,10,10,9,10,10,9,9,10,9};
vector<vi> dists_sets = {
{1,2,2,2,2,2,2},
{1,2,2,2,2,3,1},
{1,2,2,2,2,4,0},
{1,2,2,2,3,2,1},
{1,2,2,2,3,3,0},
{1,2,2,2,4,2,0},
{1,2,2,3,2,2,1},
{1,2,2,3,2,3,0},
{1,2,2,3,3,1,1},
{1,2,2,3,3,2,0},
{1,2,2,3,4,1,0},
{1,2,2,4,2,2,0},
{1,2,2,4,3,1,0},
{1,2,2,4,4,0,0},
{1,2,3,2,2,2,1},
{1,2,3,2,2,3,0},
{1,2,3,2,3,1,1},
{1,2,3,2,3,2,0},
{1,2,3,2,4,1,0},
{1,2,3,3,2,1,1},
{1,2,3,3,2,2,0},
{1,2,3,3,3,1,0},
{1,2,3,3,4,0,0},
{1,2,3,4,1,1,1},
{1,2,3,4,1,2,0},
{1,2,3,4,2,1,0},
{1,2,3,4,3,0,0},
{1,2,3,5,1,1,0},
{1,2,3,5,2,0,0},
{1,2,4,2,2,2,0},
{1,2,4,2,3,1,0},
{1,2,4,2,4,0,0},
{1,2,4,3,2,1,0},
{1,2,4,3,3,0,0},
{1,2,4,4,1,1,0},
{1,2,4,4,2,0,0},
{1,2,4,5,1,0,0},
{1,2,4,6,0,0,0},
};
vector<string> trees[16];
map<string,int> tree_map;
void gen_trees()
{
rep2(i,0,13) trees[i] = {};
trees[0].pb("");
rep2(i,1,13)
{
rep2(k,0,i)
{
if(k > i-1-k || k >= 7 || i-1-k >= 7) continue;
forall(it,trees[k])
{
forall(it2,trees[i-1-k])
{
if(it < it2) trees[i].pb("("+it+it2+")");
else trees[i].pb("("+it2+it+")");
}
}
}
}
rep(i,siz(trees[13])) tree_map[trees[13][i]] = i;
}
int n,x,y;
vi graph[50];
int cur_ind;
string sub_hash[50];
int gen_tree(string s)
{
int v = cur_ind++;
sub_hash[v] = s;
if(s == "()") return v;
string s1,s2;
int c = 0;
rep2(i,1,siz(s)-1)
{
if(s[i] == '(') c++;
else c--;
s1 += s[i];
if(c == 0) break;
}
rep2(i,siz(s1)+1,siz(s)-2) s2 += s[i];
if(siz(s1) > 0)
{
int v2 = gen_tree(s1);
graph[v].pb(v2);
graph[v2].pb(v);
}
if(siz(s2) > 0)
{
int v2 = gen_tree(s2);
graph[v].pb(v2);
graph[v2].pb(v);
}
return v;
}
map<int,int> vert_ind;
map<int,int> vert_ind2;
void bfs_inds(int v)
{
vi cur = {v};
while(siz(cur) != 0)
{
forall(it,cur)
{
vert_ind2[it] = cur_ind;
vert_ind[cur_ind++] = it;
}
vi cur2;
forall(it,cur)
{
vector<pair<string,int>> add;
forall(it2,graph[it])
{
if(siz(sub_hash[it2]) < siz(sub_hash[it])) add.pb({sub_hash[it2],it2});
}
sort(all(add));
forall(it,add) cur2.pb(it.ss);
}
cur = cur2;
}
}
int dist[50];
void bfs(int v)
{
rep(i,50) dist[i] = 1e9;
queue<pii> q;
q.push({v,0});
while(!q.empty())
{
pii t = q.front();
q.pop();
if(dist[t.ff] != 1e9) continue;
dist[t.ff] = t.ss;
forall(it,graph[t.ff]) q.push({it,t.ss+1});
}
}
const int k = 1447;
int ind[1447][1447];
bool was = 0;
void init2()
{
if(!was)
{
was = 1;
int cur = 0;
rep2(i,0,k-1)
{
rep2(j,i,k-1)
{
ind[i][j] = cur++;
}
}
}
}
pll segs[32];
}
string SendB(int N, int X, int Y)
{
n = N;
x = X;
y = Y;
if(x > y) swap(x,y);
int x2 = x/13;
int y2 = y/13;
init2();
ll ans = ind[x2][y2];
string ans2;
rep(i,20) if(ans&(1<<i)) ans2 += "1"; else ans2 += "0";
return ans2;
}
int Answer(string T)
{
ll l = 0;
ll r = 1;
rep2(i,1,31)
{
if(i == 7) continue;
segs[i] = {l,r};
ll len = (r-l+1)*(i != 8 ? 2 : 4);
l = r+1;
r = l+len-1;
}
int indx = 0;
int indy = 0;
int d = 0;
int b = 0;
int comb = 0;
gen_trees();
if(siz(T) != 7)
{
ll ans = segs[siz(T)].ff;
rep(i,siz(T)) if(T[i] == '1') ans += (1<<i);
indx = ans%siz(dists_sets);
ans /= siz(dists_sets);
d = ans%(n-1);
ans /= (n-1);
comb = ans;
rep(i,121)
{
if(comb < opt_list[i]) break;
indy++;
comb -= opt_list[i];
}
}
else rep(i,7) if(T[i] == '1') indx += (1<<i);
x %= 13;
y %= 13;
rep(i,50) graph[i] = {};
if(siz(T) == 7)
{
cur_ind = 0;
gen_tree(trees[13][indx]);
cur_ind = 0;
bfs_inds(0);
bfs(vert_ind[y]);
return dist[vert_ind[x]];
}
cur_ind = 0;
gen_tree(trees[13][indy]);
cur_ind = 0;
bfs_inds(0);
vi opts;
rep(i,13) if(siz(graph[i]) < 3) opts.pb(vert_ind2[i]);
sort(all(opts));
b = opts[comb];
bfs(vert_ind[y]);
ll distx = 0;
int cur = x;
rep(i,7)
{
if(dists_sets[indx][i] > cur)
{
distx = i;
break;
}
cur -= dists_sets[indx][i];
}
return distx+d+dist[vert_ind[b]];
}
