#include <bits/stdc++.h>

#define boAshraf ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define sz(s) (int)(s).size()
#define all(s) (s).begin(),(s).end()
using namespace std;

void File();

void sol();

const int N = 1e3;
int lpf[N + 1];
vector<int> cost[N + 1];
int val[(int)2e5+1];
vector<int> prime;

void sieve() {
    for (int i = 2; i <= N; i++) {
        if (lpf[i] == 0) {
            lpf[i] = i;
            prime.push_back(i);
        }
        for (int j: prime) {
            if (j > lpf[i] || 1LL * i * j > N)break;
            lpf[i * j] = j;
        }
    }
    for (int i = 1; i <= N; i++) {
        for (auto it: prime) {
            cost[i].emplace_back((it - (i % it)) % it);
        }
    }
}

class LCA {
    int n, logN, root = 1;
    vector<int> depth;
    vector<vector<int>> adj, lca;
    vector<vector<int>>sum;
    void dfs(int node, int parent) {
        lca[node][0] = parent;
        sum[node]=cost[val[node]];
        depth[node] = (~parent ? depth[parent] + 1 : 0);
        if(~parent){
            for (int i = 0; i < sz(prime); ++i) {
                sum[node][i]+=sum[parent][i];
            }
        }
        for (int k = 1; k <= logN; k++) {
            int up_parent = lca[node][k - 1];
            if (~up_parent) {
                lca[node][k] = lca[up_parent][k - 1];
            }
        }
        for (int child: adj[node])
            if (child != parent)
                dfs(child, node);
    }

public:
    LCA(const vector<vector<int>> &_adj, int root = 1) : root(root), adj(_adj) {
        adj = _adj;
        n = adj.size() - 1;
        logN = log2(n);
        lca = vector<vector<int>>(n + 1, vector<int>(logN + 1, -1));
        depth = vector<int>(n + 1);
        sum=vector<vector<int>>(n+1,vector<int>(sz(prime)));
        dfs(root, -1);
    }

    int get_LCA(int x, int y) {
        if (depth[x] < depth[y])
            swap(x, y);
        for (int k = logN; k >= 0; k--)
            if (depth[x] - (1 << k) >= depth[y])
                x = lca[x][k];
        if (x == y)
            return x;
        for (int k = logN; k >= 0; k--) {
            if (lca[x][k] != lca[y][k]) {
                x = lca[x][k], y = lca[y][k];
            }
        }
        return lca[x][0];
    }

    int get_sum(int u, int v) {
        int lc = get_LCA(u, v);
        int p_lc=lca[lc][0];
        int mn=1e9;
        for (int i = 0; i < sz(prime); ++i) {
            mn=min(mn,sum[u][i]+sum[v][i]-sum[lc][i]-(~p_lc?sum[p_lc][i]:0));
        }
        return mn;
    }
};

int main() {
    boAshraf
    File();
    sieve();
    int t = 1;
    cin >> t;
    while (t--) {
        sol();
    }
    return 0;
}

void sol() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> val[i];
    }
    vector<vector<int>> adj(n+1);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    LCA lc(adj);
    while(q--){
        int u,v;
        cin>>u>>v;
        cout<<lc.get_sum(u,v)<<'\n';
    }
}

void File() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}