#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define _ << " " <<
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ull unsigned long long
#define lll __int128
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define BlueCrowner ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
const ll mod = 1e9 + 7;
const ll mod1 = 998244353;
const ll naim = 1e9;
const ll max_bit = 60;
const ull tom = ULLONG_MAX;
const ll MAXN = 100005;
const ll LOG = 20;
const ll NAIM = 1e18;
const ll N = 2e6 + 5;
// ---------- GCD ----------
ll gcd(ll a, ll b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
// ---------- LCM ----------
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
// ---------- Modular Exponentiation ----------
ll modpow(ll a, ll b, ll m = mod) {
ll c = 1;
a %= m;
while (b > 0) {
if (b & 1) c = c * a % m;
a = a * a % m;
b >>= 1;
}
return c;
}
// ---------- Modular Inverse (Fermat’s Little Theorem) ----------
ll modinv(ll a, ll m = mod) {
return modpow(a, m - 2, m);
}
// ---------- Factorials and Inverse Factorials ----------
ll fact[N], invfact[N];
void pre_fact(ll n = N-1, ll m = mod) {
fact[0] = 1;
for (ll i = 1; i <= n; i++) fact[i] = fact[i-1] * i % m;
invfact[n] = modinv(fact[n], m);
for (ll i = n; i > 0; i--) invfact[i-1] = invfact[i] * i % m;
}
// ---------- nCr ----------
ll nCr(ll n, ll r, ll m = mod) {
if (r < 0 || r > n) return 0;
return fact[n] * invfact[r] % m * invfact[n-r] % m;
}
// ---------- Sieve of Eratosthenes ----------
vector<ll> primes;
bool is_prime[N];
void sieve(ll n = N-1) {
fill(is_prime, is_prime + n + 1, true);
is_prime[0] = is_prime[1] = false;
for (ll i = 2; i * i <= n; i++) {
if (is_prime[i]) {
for (ll j = i * i; j <= n; j += i)
is_prime[j] = false;
}
}
for (ll i = 2; i <= n; i++)
if (is_prime[i]) primes.pb(i);
}
vector<int> par;
int diameter_u, diameter_v, diameter_length;
vector<ll> dist_u, dist_v;
string stringu, stringv;
//diameter_u - one endpoint of the diameter that represented in base 10
//diameter_v - another endpoint of the diameter that represented in base 10
//stringu - string that represents diameter_u in base 5 (reversed)
//stringv - string that represents diameter_v in base 5 (reversed)
ll d_u_1, d_v_1; //base 10, difference of 9994 and new diameter_u/diameter_v. if diameter_u/diameter_v not in (9982, 9993) then all character equals to 0
ll d_u_2, d_v_2; //base,10 difference of 9998 and new diameter_u/diameter_v. if diameter_u/diameter_v not in (9994, 9997) then all character equals to 0
string d_u1_str, d_v1_str; //base 5 representation (reversed) of d_u_1 and d_v_1
//d_u_1
//d_v_1
int send_message(int n, int i, int pi) {
par.pb(pi);
if(i == 9981) {
ll n = par.size();
vector<vector<int>> g(n);
dist_u.resize(n);
dist_v.resize(n);
for(int j = 1; j < n; j++) {
g[j].pb(par[j]);
g[par[j]].pb(j);
}
ll x = 0;
function<void(int,int,ll)> dfs = [&](int u, int p, ll d) {
if(d > x) {
x = d;
diameter_u = u;
}
for(int v : g[u]) {
if(v != p) {
dfs(v, u, d+1);
}
}
};
dfs(0, -1, 0);
x = 0;
dfs(diameter_u, -1, 0);
diameter_length = x;
function<void(int,int,ll, bool)> dfs_dist = [&](int u, int p, ll d, bool from_u) {
if(from_u) dist_u[u] = d;
else dist_v[u] = d;
for(auto &v : g[u]) {
if(v != p) {
dfs_dist(v, u, d+1, !from_u);
}
}
};
dfs_dist(diameter_u, -1, 0, 1);
dfs_dist(diameter_v, -1, 0, 0);
ll temp1 = diameter_u, temp2 = diameter_v;
while(temp1) {
stringu.pb((temp1 % 5) + '0');
temp1 /= 5;
}
while(temp2) {
stringv.pb((temp2 % 5) + '0');
temp2 /= 5;
}
return 0;
}
else if(i > 9981 && i <= 9987) {
if(dist_u[pi] + 1 > diameter_length) {
diameter_v = i;
diameter_length = dist_u[pi] + 1;
dist_u.pb(dist_u[pi] + 1);
dist_v.pb(0);
dist_v.assign(i + 1, 0);
queue<int> q;
q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto &v : g[u]) {
if(dist_v[v] == 0 && v != diameter_u) {
dist_v[v] = dist_v[u] + 1;
q.push(v);
}
}
}
stringv = "";
ll temp2 = diameter_v;
while(temp2) {
stringv.pb((temp2 % 5) + '0');
temp2 /= 5;
}
}
else if(dist_v[pi] + 1 > diameter_length) {
diameter_u = i;
diameter_length = dist_v[pi] + 1;
dist_v.pb(dist_v[pi] + 1);
dist_u.pb(0);
dist_u.assign(i + 1, 0);
queue<int> q;
q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto &v : g[u]) {
if(dist_u[v] == 0 && v != diameter_v) {
dist_u[v] = dist_u[u] + 1;
q.push(v);
}
}
}
stringu = "";
ll temp1 = diameter_u;
while(temp1) {
stringu.pb((temp1 % 5) + '0');
temp1 /= 5;
}
}
ll j = i - 9982;
return (j < stringu.size()) ? (stringu[j] - '0') : 0;
}
else if(i > 9987 && i <= 9993) {
if(dist_v[pi] + 1 > diameter_length) {
diameter_u = i;
diameter_length = dist_v[pi] + 1;
dist_v.pb(dist_v[pi] + 1);
dist_u.pb(0);
dist_u.assign(i + 1, 0);
queue<int> q;
q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto &v : g[u]) {
if(dist_u[v] == 0 && v != diameter_v) {
dist_u[v] = dist_u[u] + 1;
q.push(v);
}
}
}
stringu = "";
ll temp1 = diameter_u;
while(temp1) {
stringu.pb((temp1 % 5) + '0');
temp1 /= 5;
}
}
else if(dist_u[pi] + 1 > diameter_length) {
diameter_v = i;
diameter_length = dist_u[pi] + 1;
dist_u.pb(dist_u[pi] + 1);
dist_v.pb(0);
dist_v.assign(i + 1, 0);
queue<int> q;
q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto &v : g[u]) {
if(dist_v[v] == 0 && v != diameter_u) {
dist_v[v] = dist_v[u] + 1;
q.push(v);
}
}
}
stringv = "";
ll temp2 = diameter_v;
while(temp2) {
stringv.pb((temp2 % 5) + '0');
temp2 /= 5;
}
}
if(i == 9993) {
if(diameter_u > 9981 && diameter_u < 9994) {
d_u_1 = 9994 - diameter_u;
string d_u1_str = "";
ll temp1 = d_u_1;
while(temp1) {
d_u1_str.pb((temp1 % 5) + '0');
temp1 /= 5;
}
}
if(diameter_v > 9981 && diameter_v < 9994) {
d_v_1 = 9994 - diameter_v;
string d_v1_str = "";
ll temp2 = d_v_1;
while(temp2) {
d_v1_str.pb((temp2 % 5) + '0');
temp2 /= 5;
}
}
}
ll j = i - 9988;
return (j < stringv.size()) ? (stringv[j] - '0') : 0;
}
if(i > 9993 && i <= 9995) {
ll j = i - 9994;
return (j < d_u1_str.size()) ? (d_u1_str[j] - '0') : 0;
}
else if(i > 9995 && i <= 9997) {
if(i == 9997) {
if(diameter_u > 9993 && diameter_u <= 9997) {
d_u_2 = 9998 - diameter_u;
}
if(diameter_v > 9993 && diameter_v <= 9997) {
d_v_2 = 9998 - diameter_v;
}
}
ll j = i - 9996;
return (j < d_v1_str.size()) ? (d_v1_str[j] - '0') : 0;
}
else if(i == 9998) {
return d_v_2;
}
else if(i == 9999) {
return d_u_2;
}
}
void solve() {
}
int main() {
BlueCrowner;
ll t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
