/******************************************
* AUTHOR : RAJAGOPALAN *
* NICK : ARNO *
* INSTITUTION : VIT *
******************************************/
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define alli(a, n, k) (a + k), (a + n + k)
#define FP(i, a, b, k) for (__typeof(a) i = a; i < b; i += k)
#define FS(i, a, b, k) for (__typeof(a) i = a; i > b; i -= k)
#define IT(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;
template <class T>
inline T gcd(T x, T y)
{
if (!y)
return x;
return gcd(y, x % y);
}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector<pair<int, int>> VPII;
typedef vector<pair<int, PII>> VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;
inline ll modulo(ll a, ll m)
{
return (a % m + m) % m;
}
inline ll modInverse(ll a, ll m)
{
assert(__gcd(a, m) == 1);
ll m0 = m;
ll y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1)
{
ll q = a / m;
ll t = m;
m = a % m, a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0)
x += m0;
return x;
}
inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
if (y == 0)
return 1LL;
else if (y == 1)
return x;
else
{
ll ans = modPow(x, y / 2, m) % m;
if (y & 1)
{
return (((ans * ans) % m) * x) % m;
}
else
{
return (ans * ans) % m;
}
}
}
vector<VII> adj(10001);
vector<bool> vis(10001);
vector<int> depth(10001);
unordered_map<int,bool> nR;
int D,n;
void bfs(int r,vector<VII>& par)
{
queue<int> q;
q.push(r);
depth[r]=0;
vis[r]=true;
while(!q.empty())
{
int u=q.front();
q.pop();
for(auto it:adj[u])
if(!vis[it])
{
vis[it]=true;
q.push(it);
depth[it]=depth[u]+1;
par[0][it]=u;
}
}
//cout<<"HERE"<<endl;
}
int walk(int i,int k,vector<VII>& par)
{
for(int d=0;d<=D && i!=-1;++d)
if((1<<d) && k)i=par[d][i];
return i;
}
int LCA(int u,int v,vector<VII>& par)
{
if(depth[u]>depth[v])
u=walk(u,depth[u]-depth[v],par);
else if(depth[u]<depth[v])
v=walk(v,depth[v]-depth[u],par);
if(u==v)
return u;
for(int d=D;d>=0;--d)
{
if(par[d][u]!=par[d][v])
{
u=par[d][u];
v=par[d][v];
}
}
return par[0][u];
}
int main(int argc, char *argv[])
{
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
for(int i=1;i<=t;++i)
{
cin>>n;
nR.clear();
for(int i=0;i<n;++i)
{
adj[i].clear();
depth[i]=0;
vis[i]=false;
}
for(int i=1;i<=n;++i)
{
int sz;
cin>>sz;
int sx;
for(int j=0;j<sz;++j)
{
cin>>sx;
adj[i-1].pb(sx-1);
nR[sx-1]=true;
//adj[sx-1].pb(i-1);
}
}
int root;
for(int i=0;i<n;++i)
if(!nR[i]){
root=i;
}
//cout<<"HERE"<<endl;
D=log2(n);
vector<VII> par(D+1,VII(n,-1));
bfs(root,par);
//cout<<"HERE1"<<endl;
for(int i=0;i<n;++i)
{
for(int d=1;d<=D;++d)
{
int mid=par[d-1][i];
if(mid!=-1)
par[d][i]=par[d-1][mid];
}
}
//cout<<"HERE2"<<endl;
int q;
cin>>q;
cout<<"Case "<<t<<":\n";
while(q--)
{
int x,y;
cin>>x>>y;
cout<<1+LCA(x-1,y-1,par)<<endl;
}
}
return 0;
}
LyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKgoqIEFVVEhPUiA6IFJBSkFHT1BBTEFOICoKKiBOSUNLIDogQVJOTyAqCiogSU5TVElUVVRJT04gOiBWSVQgKgoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgojaW5jbHVkZSA8ZXh0L3BiX2RzL2RldGFpbC9zdGFuZGFyZF9wb2xpY2llcy5ocHA+CgojZGVmaW5lIGxsIGxvbmcgbG9uZwojZGVmaW5lIHVsbCB1bnNpZ25lZCBsb25nIGxvbmcKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBhbGwoeCkgKHgpLmJlZ2luKCksICh4KS5lbmQoKQojZGVmaW5lIGFsbGkoYSwgbiwgaykgKGEgKyBrKSwgKGEgKyBuICsgaykKI2RlZmluZSBGUChpLCBhLCBiLCBrKSBmb3IgKF9fdHlwZW9mKGEpIGkgPSBhOyBpIDwgYjsgaSArPSBrKQojZGVmaW5lIEZTKGksIGEsIGIsIGspIGZvciAoX190eXBlb2YoYSkgaSA9IGE7IGkgPiBiOyBpIC09IGspCiNkZWZpbmUgSVQoaXQsIGEpIGZvciAoX190eXBlb2YoYS5iZWdpbigpKSBpdCA9IGEuYmVnaW4oKTsgaXQgIT0gYS5lbmQoKTsgKytpdCkKI2RlZmluZSBlcHMgMWUtNgojZGVmaW5lIHBpIDMuMTQxNTkyNjUzNTg5NzkzCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwoKdGVtcGxhdGUgPGNsYXNzIFQ+CmlubGluZSBUIGdjZChUIHgsIFQgeSkKewoJaWYgKCF5KQoJCXJldHVybiB4OwoJcmV0dXJuIGdjZCh5LCB4ICUgeSk7Cn0KdHlwZWRlZiB2ZWN0b3I8aW50PiBWSUk7CnR5cGVkZWYgdmVjdG9yPGxsPiBWTEw7CnR5cGVkZWYgcGFpcjxpbnQsIGludD4gUElJOwp0eXBlZGVmIHZlY3RvcjxwYWlyPGludCwgaW50Pj4gVlBJSTsKdHlwZWRlZiB2ZWN0b3I8cGFpcjxpbnQsIFBJST4+IFZQUEk7CmNvbnN0IGludCBNT0QgPSAxZTkgKyA3Owpjb25zdCBpbnQgSU5GID0gMWU5OwoKaW5saW5lIGxsIG1vZHVsbyhsbCBhLCBsbCBtKQp7CglyZXR1cm4gKGEgJSBtICsgbSkgJSBtOwp9CgppbmxpbmUgbGwgbW9kSW52ZXJzZShsbCBhLCBsbCBtKQp7Cglhc3NlcnQoX19nY2QoYSwgbSkgPT0gMSk7CglsbCBtMCA9IG07CglsbCB5ID0gMCwgeCA9IDE7CgoJaWYgKG0gPT0gMSkKCQlyZXR1cm4gMDsKCgl3aGlsZSAoYSA+IDEpCgl7CgkJbGwgcSA9IGEgLyBtOwoJCWxsIHQgPSBtOwoKCQltID0gYSAlIG0sIGEgPSB0OwoJCXQgPSB5OwoKCQl5ID0geCAtIHEgKiB5OwoJCXggPSB0OwoJfQoKCWlmICh4IDwgMCkKCQl4ICs9IG0wOwoKCXJldHVybiB4Owp9CgppbmxpbmUgbGwgbW9kUG93KGxsIHgsIGxsIHksIGxsIG0pCnsgLy94XnkgJSBtCglpZiAoeSA9PSAwKQoJCXJldHVybiAxTEw7CgllbHNlIGlmICh5ID09IDEpCgkJcmV0dXJuIHg7CgllbHNlCgl7CgkJbGwgYW5zID0gbW9kUG93KHgsIHkgLyAyLCBtKSAlIG07CgkJaWYgKHkgJiAxKQoJCXsKCQkJcmV0dXJuICgoKGFucyAqIGFucykgJSBtKSAqIHgpICUgbTsKCQl9CgkJZWxzZQoJCXsKCQkJcmV0dXJuIChhbnMgKiBhbnMpICUgbTsKCQl9Cgl9Cn0KdmVjdG9yPFZJST4gYWRqKDEwMDAxKTsKdmVjdG9yPGJvb2w+IHZpcygxMDAwMSk7CnZlY3RvcjxpbnQ+IGRlcHRoKDEwMDAxKTsKdW5vcmRlcmVkX21hcDxpbnQsYm9vbD4gblI7CmludCBELG47CnZvaWQgYmZzKGludCByLHZlY3RvcjxWSUk+JiBwYXIpCnsKCXF1ZXVlPGludD4gcTsKCXEucHVzaChyKTsKCWRlcHRoW3JdPTA7Cgl2aXNbcl09dHJ1ZTsKCXdoaWxlKCFxLmVtcHR5KCkpCgl7CgkJaW50IHU9cS5mcm9udCgpOwoJCXEucG9wKCk7CgkJZm9yKGF1dG8gaXQ6YWRqW3VdKQoJCWlmKCF2aXNbaXRdKQoJCXsKCQkJdmlzW2l0XT10cnVlOwoJCQlxLnB1c2goaXQpOwoJCQlkZXB0aFtpdF09ZGVwdGhbdV0rMTsKCQkJcGFyWzBdW2l0XT11OwoJCX0KCX0KCS8vY291dDw8IkhFUkUiPDxlbmRsOwp9CmludCB3YWxrKGludCBpLGludCBrLHZlY3RvcjxWSUk+JiBwYXIpCnsKCWZvcihpbnQgZD0wO2Q8PUQgJiYgaSE9LTE7KytkKQoJaWYoKDE8PGQpICYmIGspaT1wYXJbZF1baV07CgoJcmV0dXJuIGk7Cn0KaW50IExDQShpbnQgdSxpbnQgdix2ZWN0b3I8VklJPiYgcGFyKQp7CglpZihkZXB0aFt1XT5kZXB0aFt2XSkKCXU9d2Fsayh1LGRlcHRoW3VdLWRlcHRoW3ZdLHBhcik7CgllbHNlIGlmKGRlcHRoW3VdPGRlcHRoW3ZdKQoJdj13YWxrKHYsZGVwdGhbdl0tZGVwdGhbdV0scGFyKTsKCglpZih1PT12KQoJcmV0dXJuIHU7CgoJZm9yKGludCBkPUQ7ZD49MDstLWQpCgl7CgkJaWYocGFyW2RdW3VdIT1wYXJbZF1bdl0pCgkJewoJCQl1PXBhcltkXVt1XTsKCQkJdj1wYXJbZF1bdl07CgkJfQoJfQoJcmV0dXJuIHBhclswXVt1XTsKfQppbnQgbWFpbihpbnQgYXJnYywgY2hhciAqYXJndltdKQp7Cglpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4udGllKE5VTEwpOwoJaW50IHQ7CgljaW4+PnQ7Cglmb3IoaW50IGk9MTtpPD10OysraSkKCXsKCQljaW4+Pm47CgkJblIuY2xlYXIoKTsKCQlmb3IoaW50IGk9MDtpPG47KytpKQoJCXsKCQkJYWRqW2ldLmNsZWFyKCk7CgkJCWRlcHRoW2ldPTA7CgkJCXZpc1tpXT1mYWxzZTsKCQl9CgkJZm9yKGludCBpPTE7aTw9bjsrK2kpCgkJewoJCQlpbnQgc3o7CgkJCWNpbj4+c3o7CgkJCWludCBzeDsKCQkJZm9yKGludCBqPTA7ajxzejsrK2opCgkJCXsKCQkJCWNpbj4+c3g7CgkJCQlhZGpbaS0xXS5wYihzeC0xKTsKCQkJCW5SW3N4LTFdPXRydWU7CgkJCQkvL2FkaltzeC0xXS5wYihpLTEpOwoJCQl9CgkJfQoJCWludCByb290OwoJCWZvcihpbnQgaT0wO2k8bjsrK2kpCgkJaWYoIW5SW2ldKXsKCQkJcm9vdD1pOwoJCX0KCQkvL2NvdXQ8PCJIRVJFIjw8ZW5kbDsKCQlEPWxvZzIobik7CgkJdmVjdG9yPFZJST4gcGFyKEQrMSxWSUkobiwtMSkpOwoJCWJmcyhyb290LHBhcik7CgkJLy9jb3V0PDwiSEVSRTEiPDxlbmRsOwoJCWZvcihpbnQgaT0wO2k8bjsrK2kpCgkJewoJCQlmb3IoaW50IGQ9MTtkPD1EOysrZCkKCQkJewoJCQkJaW50IG1pZD1wYXJbZC0xXVtpXTsKCQkJCWlmKG1pZCE9LTEpCgkJCQlwYXJbZF1baV09cGFyW2QtMV1bbWlkXTsKCQkJfQoJCX0KCQkvL2NvdXQ8PCJIRVJFMiI8PGVuZGw7CgoJCWludCBxOwoJCWNpbj4+cTsKCQljb3V0PDwiQ2FzZSAiPDx0PDwiOlxuIjsKCQl3aGlsZShxLS0pCgkJewoJCQlpbnQgeCx5OwoJCQljaW4+Png+Pnk7CgkJCWNvdXQ8PDErTENBKHgtMSx5LTEscGFyKTw8ZW5kbDsKCQl9Cgl9CglyZXR1cm4gMDsKfQ==