#include <iostream>
#include <fstream>
#include <cstdlib>
#include <climits>
#include <iomanip>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <iterator>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>
#include <stack>
#include <bitset>
#include <functional>
#include <utility>
#include <cmath>
#include <string>
#include <deque>
#include <array>
#include <tuple>
#include <cstring>
#include <ctime>
#include <random>
#include <chrono>
///#include <windows.h>

#pragma GCC optimize("fast-math")

#define ll long long
#define ld long double
#define pll pair<ll, ll>
#define psi pair<short int, short int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin() + 1, (x).end()
#define all0(x) (x).begin(), (x).end()
#define allrev(x) (x).rbegin(), (x).rend() - 1
#define allrev0(x) (x).rbegin(), (x).rend()
#define println(thing) cout << thing << '\n'
#define yes println("YES")
#define no println("NO")
#define maybe println("MAYBE")
#define mda println("/////////////////")
#define msb(x) ((x) == 0 ? 0 : (1 << (64 - __builtin_clzll(x) - 1)))
#define lsb(x) ((x) & (-x))

using namespace std;

mt19937_64 rng(chrono :: steady_clock :: now().time_since_epoch().count());

const size_t fixed_random = rng();

clock_t start_time = clock(), end_time;

ll random_seed(ll modulo) {
    return rng() % modulo;
}

template <typename T>
inline void hash_combine(size_t& seed, const T& value) {
    seed ^= hash<T>{}(value) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct pair_hash {
    template <typename T1, typename T2>
    size_t operator () (const pair<T1, T2>& p) const {
        size_t seed = fixed_random;

        hash_combine(seed, p.first);
        hash_combine(seed, p.second);

        return seed;
    }
};

struct normal_hash {
    template <typename T>
    size_t operator () (const T& p) const {
        size_t seed = fixed_random;

        hash_combine(seed, p);

        return seed;
    };
};

template <typename unordered_Map>
void optimize_map(unordered_Map& M) {
    M.reserve(1024);
    M.max_load_factor(0.5);
}

template <typename T1, typename T2>
istream& operator >> (istream& in, pair<T1, T2>& p) {
    in >> p.first >> p.second;
    return in;
}

template <typename T1, typename T2>
ostream& operator << (ostream& out, pair<T1, T2>& p) {
    out << p.first << ' ' << p.second;
    return out;
}

/// for bitset bits
template <typename T1, typename T2> T1 operator ^= (T1 t1, T2 t2) {t1 = t1 ^ t2; return t1;}
template <typename T1, typename T2> T1 operator |= (T1 t1, T2 t2) {t1 = t1 | t2; return t1;}
template <typename T1, typename T2> T1 operator &= (T1 t1, T2 t2) {t1 = t1 & t2; return t1;}

const ll NMX = (ll) 1e6;
const ll MOD = (ll) 998244353;
const ll INF = (ll) 1e17;

ll binExp(ll base, ll exp) {
    ll P = 1;
    for (ll bit = 1; bit <= exp; bit <<= 1) {
        if (exp & bit)
            P = (P * base) % MOD;
        base = (base * base) % MOD;
    }
    return P;
}

inline ll modInv(ll x) {
    return binExp(x, MOD - 2);
}

ll test_case = 0;

void solve(ll testcase)
{
    ll n;
    cin >> n;

    vector<ll> a(n + 1);

    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<vector<ll>> g(n + 1);

    for (ll i = 1, v, u; i <= n - 1; i++) {
        cin >> v >> u;

        g[v].emplace_back(u);
        g[u].emplace_back(v);
    }

    vector<ll> pv(n + 1);

    function<void(ll, ll)> set_parents = [&](ll v, ll par) {
        for (ll u : g[v]) {
            if (u != par) {
                pv[u] = v;
                set_parents(u, v);
            }
        }
    };

    set_parents(1, -1);

    const ll LOG = log2(n);

    vector<vector<ll>> jump(n + 1, vector<ll>(LOG + 1, 0));
    vector<vector<ll>> bitwise_or(n + 1, vector<ll>(LOG + 1, 0));

    for (ll i = 1; i <= n; i++) {
        jump[i][0] = pv[i];
        bitwise_or[i][0] = a[i];
    }

    for (ll j = 1; j <= LOG; j++) {
        for (ll i = 1; i <= n; i++) {
            jump[i][j] = jump[jump[i][j - 1]][j - 1];
            bitwise_or[i][j] = bitwise_or[i][j - 1] | bitwise_or[jump[i][j - 1]][j - 1];
        }
    }

    ll time = 0;

    vector<ll> time_in(n + 1);
    vector<ll> time_out(n + 1);

    time_out[0] = LLONG_MAX;

    function<void(ll, ll)> dfs = [&](ll v, ll par) {
        time_in[v] = ++time;

        for (ll u : g[v]) {
            if (u != par) {
                dfs(u, v);
            }
        }

        time_out[v] = ++time;
    };

    function<bool(ll, ll)> is_ancestor = [&](ll v, ll u) {
        return time_in[u] <= time_in[v] && time_out[u] >= time_out[v];
    };

    function<ll(ll, ll)> LCA = [&](ll v, ll u) {
        if (is_ancestor(v, u)) {
            return u;
        }
        if (is_ancestor(u, v)) {
            return v;
        }
        for (ll bit = LOG; bit >= 0; bit--) {
            if (!is_ancestor(u, jump[v][bit])) {
                v = jump[v][bit];
            }
        }
        return jump[v][0];
    };

    function<ll(ll, ll)> path_or = [&](ll v, ll ancestor) {
        if (v == ancestor) {
            return a[v];
        }

        ll to_return = 0;

        for (ll bit = LOG; bit >= 0; bit--) {
            if (!is_ancestor(ancestor, jump[v][bit])) {
                to_return |= bitwise_or[v][bit];
                v = jump[v][bit];
            }
        }

        return to_return | bitwise_or[v][1];
    };

    ll q;
    cin >> q;

    for (ll qq = 1, v, u; qq <= q; qq++) {
        cin >> v >> u;

        if (v == u) {
            cout << 2 * __builtin_popcountll(a[v]) << ' ';
            continue;
        }

        ll ancestor = LCA(v, u);

        if (ancestor == u) {
            cout << __builtin_popcountll(path_or(v, ancestor)) + max(__builtin_popcountll(a[v]), __builtin_popcountll(a[u])) << ' ';
        }
        else if (ancestor == v) {
            cout << __builtin_popcountll(path_or(u, ancestor)) + max(__builtin_popcountll(a[v]), __builtin_popcountll(a[u])) << ' ';
        }
        else {
            cout << __builtin_popcountll(path_or(v, ancestor)) + __builtin_popcountll(path_or(u, ancestor)) << ' ';
        }
    }

    return cout << '\n', void();
}

int main(void)
{
    ///freopen("lca.in", "r", stdin);
    ///freopen("lca.out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

    ///cout << fixed << setprecision(20);

    ll tt; cin >> tt; while (tt--)
       solve(++test_case);
    \

    return 0;
}

/**

///

**/