def solve():
    n = int(input())
    x = 0
    c = 1
    while -n <= x <= n:
        if c % 2 == 1:
            x -= 2 * c - 1
        else:
            x += 2 * c - 1
        c += 1
    if c % 2 == 0:
        print("Sakurako")
    else:
        print("Kosuke")


for tc in range(int(input())):
    solve()

def solve():
    n = int(input())
    mn = dict()
    for i in range(n):
        a = [int(x) for x in input().split()]
        for j in range(n):
            mn[i - j] = min(a[j], mn.get(i - j, 0))
    ans = 0
    for value in mn.values():
        ans -= value
    print(ans)
 
t = int(input())
for _ in range(t):
    solve()

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n+1];
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=n/2-1;i>=1;i--){
            if(a[i]==a[i+1] || a[n-i+1]==a[n-i]){
                swap(a[i],a[n-i+1]);
            }
        }
        int re=0;
        for(int i=1;i<n;i++){
            re+=(a[i]==a[i+1]);
        }
        cout<<re<<endl;
    }
}

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int a[n+1];
        map<int,int>mp;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        int p_su[n+1];
        p_su[0]=0;
        int lst[n+1];
        mp[0]=0;
        for(int i=1;i<=n;i++){
            p_su[i]=p_su[i-1]+a[i];
            if(mp.find(p_su[i])==mp.end()){
                lst[i]=-1;
            }
            else{
                lst[i]=mp[p_su[i]];
            }
            mp[p_su[i]]=i;
        }
        int dp[n+1];
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++){
            dp[i]=max(dp[i],dp[i-1]);
            if(lst[i]!=-1){
                dp[i]=max(dp[i],dp[lst[i]]+1);
            }
        }
        cout<<*max_element(dp,dp+n+1)<<endl;
    }
}

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int p[n+1];
        for(int i=1;i<=n;i++){
            cin>>p[i];
        }
        bool us[n+1];
        memset(us,0,sizeof us);
        int re=0;
        for(int i=1;i<=n;i++){
            if(!us[i]){
                int cu=i;
                int le=0;
                while(us[cu]==0){
                    le++;
                    us[cu]=1;
                    cu=p[cu];
                }
                re+=(le-1)/2;
            }
        }
        cout<<re<<'\n';
    }
}

#include <bits/stdc++.h>
 
using namespace std;
using LL = long long;
#define ssize(x) (int)(x.size())
#define ALL(x) (x).begin(), (x).end()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int rd(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}
const LL MOD = 1e9 + 7;
int bp(int a, int n) {
    if (n == 0)
        return 1;
    if (n % 2 == 0)
        return bp(1LL * a * a % MOD, n / 2);
    else
        return 1LL * bp(a, n - 1) * a % MOD;
}
int inv(int a) {
    return bp(a, MOD - 2);
}
void solve() {
    LL n, k;
    cin >> n >> k;
    n %= MOD;
    if (k == 1) {
        cout << n << "\n";
        return;
    }
    vector<int> fib(3);
    fib[0] = fib[1] = 1;
    int cnt = 0;
    for (int i = 2; i <= 10 * k; i++) {
        fib[i % 3] = (fib[(i + 2) % 3] + fib[(i + 1) % 3]) % k;
        if (fib[i % 3] == 0)
            cnt++;
        if (fib[i % 3] == 1 && fib[(i + 2) % 3] == 0) {
            cout << 1LL * i * n % MOD * inv(cnt) % MOD << "\n";
            return;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
     cin >> t;
    while (t--) {
        solve();
    }
}

#include <bits/stdc++.h>
 
//#define int long long
#define pb emplace_back
#define mp make_pair
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
typedef long double ld;
typedef long long ll;
 
using namespace std;
 
mt19937 rnd(time(nullptr));
 
const int inf = 1e9;
const int M = 1e9 + 7;
const ld pi = atan2(0, -1);
const ld eps = 1e-6;
 
void precalc(int v, int p, vector<vector<int>> &sl, vector<pair<int, int>> &maxd, vector<int> &h){
    maxd[v] = {0, 0};
    if (v != p) h[v] = h[p] + 1;
    for(int u: sl[v]){
        if (u == p) continue;
        precalc(u, v, sl, maxd, h);
        if (maxd[v].y < maxd[u].x + 1) {
            maxd[v].y = maxd[u].x + 1;
        }
        if (maxd[v].y > maxd[v].x) {
            swap(maxd[v].x, maxd[v].y);
        }
    }
}
 
void calc_binups(int v, int p, vector<vector<int>> &sl, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){
    binup[v][0] = {maxd[p].x, p};
    if (maxd[p].x == maxd[v].x + 1) {
        binup[v][0].x = maxd[p].y;
    }
    binup[v][0].x -= h[p];
    for(int i = 1; i < 20; ++i){
        binup[v][i].y = binup[binup[v][i - 1].y][i - 1].y;
        binup[v][i].x = max(binup[v][i - 1].x, binup[binup[v][i - 1].y][i - 1].x);
    }
 
    for(int u: sl[v]){
        if (u == p) continue;
        calc_binups(u, v, sl, binup, maxd, h);
    }
}
 
int get_ans(int v, int k, vector<vector<pair<int, int>>> &binup, vector<pair<int, int>> &maxd, vector<int> &h){
    k = min(k, h[v]);
    int res = maxd[v].x - h[v];
    int ini = h[v];
    for(int i = 19; i >= 0; --i){
        if ((1 << i) <= k) {
            res = max(res, binup[v][i].x);
            v = binup[v][i].y;
            k -= (1 << i);
        }
    }
    return res + ini;
}
 
void solve(int tc){
    int n;
    cin >> n;
    vector<vector<int>> sl(n);
    for(int i = 1; i < n; ++i){
        int u, v;
        cin >> u >> v;
        sl[--u].emplace_back(--v);
        sl[v].emplace_back(u);
    }
    vector<pair<int, int>> maxd(n);
    vector<int> h(n);
    precalc(0, 0, sl, maxd, h);
    vector<vector<pair<int, int>>> binup(n, vector<pair<int, int>>(20));
    calc_binups(0, 0, sl, binup, maxd, h);
    int q;
    cin >> q;
    for(int _ = 0; _ < q; ++_){
        int v, k;
        cin >> v >> k;
        cout << get_ans(v - 1, k, binup, maxd, h) << " ";
    }
}
 
bool multi = true;
 
signed main() {
    int t = 1;
    if (multi)cin >> t;
    for (int i = 1; i <= t; ++i) {
        solve(i);
        cout << "\n";
    }
    return 0;
}