#include <immintrin.h>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,abm,mmx,avx,avx2,popcnt,tune=native")
#define int long long
#define debug(x) cerr << #x << " = " << (x) << endl
#define ext __gnu_pbds
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define endl "\n"
using namespace std;
//using namespace ext;
const int N = 2e5 + 10;
const int MOD = 998244353; // 1000000007 1000000009 998244353
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int T = 1;
//template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
inline int power(int x, int k = MOD - 2, int mod = MOD){int res = 1; x %= mod; assert(k >= 0); for (; k; k >>= 1){if (k & 1) res = res * x % mod; x = x * x % mod;} return res;}
template <typename T>
inline void fin(T &x){
char ch = getchar(); bool f = false; x = 0;
while (!isdigit(ch)) f = ch == '-', ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
x = f ? -x : x;
}
namespace IO {char buf[120];}
template <typename T>
inline void fout(T x, const bool pt = true, const char aft = '\n'){
if (x < 0) putchar('-'), x = -x;
int top = 0;
do {IO::buf[++ top] = x % 10 + '0';} while (x /= 10);
while (top) putchar(IO::buf[top --]);
if (pt) putchar(aft);
}
int n, dep[N], f[N][__lg(N)];
using pii = pair<int, int>;
pii p0[N][__lg(N)], p1[N][__lg(N)];
vector<pii>g[N];
void solve(){
cin >> n;
for (int i = 1; i <= n; i ++) g[i].resize(0);
for (int i = 0; i < n - 1; i ++){
int u, v;
char c;
cin >> u >> v >> c;
g[u].pb({v, c == ')'}), g[v].pb({u, c == ')'});
}
auto dfs = [&](auto &self, int u, int fa, int t) -> void {
dep[u] = dep[fa] + 1, f[u][0] = fa, p0[u][0] = p1[u][0] = {t == 1, !t};
for (int i = 1; i <= __lg(dep[u]); i ++){
f[u][i] = f[f[u][i - 1]][i - 1];
if (1){
auto [l, lm] = p0[u][i - 1];
auto [rm, r] = p0[f[u][i - 1]][i - 1];
if (lm >= rm) r += lm - rm;
else l += rm - lm;
p0[u][i] = {l, r};
}
if (1){
auto [l, lm] = p1[f[u][i - 1]][i - 1];
auto [rm, r] = p1[u][i - 1];
if (lm >= rm) r += lm - rm;
else l += rm - lm;
p1[u][i] = {l, r};
}
}
for (auto [v, t] : g[u]) if (v != fa) self(self, v, u, t);
};
dfs(dfs, 1, 0, -1);
auto lca = [&](int u, int v) -> int {
if (dep[u] < dep[v]) swap(u, v);
while (dep[u] != dep[v]) u = f[u][__lg(dep[u] - dep[v])];
if (u == v) return u;
for (int i = __lg(dep[u]); i >= 0; i --) if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][0];
};
auto path0 = [&](int u, int l) -> pii {
pii res = {0, 0};
int dis = dep[u] - dep[l];
for (int i = __lg(dis); i >= 0; i --) if (dep[f[u][i]] >= dep[l]){
auto [l, lm] = res;
auto [rm, r] = p0[u][i];
if (lm >= rm) r += lm - rm;
else l += rm - lm;
res = {l, r};
u = f[u][i];
}
return res;
};
auto path1 = [&](int l, int v) -> pii {
pii res = {0, 0};
int dis = dep[v] - dep[l];
for (int i = __lg(dis); i >= 0; i --) if (dep[f[v][i]] >= dep[l]){
auto [l, lm] = p1[v][i];
auto [rm, r] = res;
if (lm >= rm) r += lm - rm;
else l += rm - lm;
res = {l, r};
v = f[v][i];
}
return res;
};
int q;
cin >> q;
while (q --){
int u, v;
cin >> u >> v;
int mid = lca(u, v);
auto [l, lm] = path0(u, mid);
auto [rm, r] = path1(mid, v);
if (lm >= rm) r += lm - rm;
else l += rm - lm;
cout << dep[u] + dep[v] - 2 * dep[mid] - l - r << endl;
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//cout << fixed << setprecision(20);
cin >> T;
while (T --){solve();}
return 0;
}
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]
#pragma GCC optimize(“Ofast,no-stack-protector,unroll-loops,fast-math”)
#pragma GCC target(“sse,sse2,sse3,ssse3,sse4.1,sse4.2,abm,mmx,avx,avx2,popcnt,tune=native”)
#define int long long
#define debug(x) cerr << #x << ” = ” << x << endl
#define ext __gnu_pbds
#define pb push_back
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using namespace ext;
const int N = 2e5 + 10;
const int MOD = 1000000009; // 1000000007 1000000009 998244353
int t = 1;
inline int power(int x, int k = MOD - 2, int mod = MOD){int res = 1; x %= mod; assert(k >= 0); for (; k; k >>= 1){if (k & 1) res = res * x % mod; x = x * x % mod;} return res;}
template [HTML_REMOVED]
inline void fin(T &x){
char ch = getchar(); bool f = false;
while (!isdigit(ch)) f = ch == ‘-‘, ch = getchar();
while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
x = f ? -x : x;
}
namespace IO {char buf[120];}
template [HTML_REMOVED]
inline void fout(T x, const bool pt = true, const char aft = ‘\n’){
if (x < 0) putchar(‘-‘), x = -x;
int top = 0;
do {IO::buf[++ top] = x % 10 + ‘0’;} while (x /= 10);
while (top) putchar(IO::buf[top –]);
if (pt) putchar(aft);
}
struct matrix{
static const int ord = 25;
int m[ord][ord]{};
int n;
int mod = MOD;
matrix(int n){
this->n = n;
init(n);
}
matrix(int n, int mod){
this->n = n;
this->mod = mod;
init(n);
}
void init(int n, int v = 0){
for (int i = 0; i < n; i )
for (int j = 0; j < n; j )
m[i][j] = v;
}
void unit(){
for (int i = 0; i < n; i ++) m[i][i] = 1;
}
inline matrix operator=(matrix other){
matrix tem(n, mod);
for (int i = 0; i < n; i )
for (int j = 0; j < n; j )
for (int k = 0; k < n; k ++)
(tem.m[i][j] += m[i][k] * other.m[k][j] + mod) %= mod;
memcpy(m, tem.m, sizeof tem.m);
return (this);
}
inline matrix operator(matrix other) const{
return matrix(this) *= other;
}
};
matrix mtx_pow(matrix x, int k, int mod = MOD){
matrix res(x.n, mod);
res.unit();
assert(k >= 0);
for (; k; k >>= 1){
if (k & 1) res = x;
x = x;
}
return res;
}
int n, m, k, d, h[20], g[25][25], ans[20], cnt;
void solve(){
cin >> n >> m >> k >> d;
for (int i = 0; i < k; i ) cin >> h[i], h[i] –;
for (int i = 0; i < m; i ){
int u, v;
cin >> u >> v;
g[u][v] = g[v][u] = 1;
}
for (int i = 0; i <= (1 << k) - 1; i ){
matrix f(n), dp(n);
for (int j = 0; j < n; j ) for (int l = 0; l < n; l ) f.m[j][l] = g[j + 1][l + 1];
for (int j = 0; j < n; j ) dp.m[0][j] = 1;
int cur = 0;
while (cur < k){
if ((i >> cur) & 1){
for (int j = 0; j < n; j ++) f.m[j][h[cur]] = f.m[h[cur]][j] = 0;
dp.m[0][h[cur]] = 0;