#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <stack>

using namespace std;

int main()
{
    int n, temp1, temp2, i;
    cin >> n;

    vector<int> value(n);
    for (i = 0; i < n; i++) {
        cin >> value[i];
    }

    vector<vector<int>> map(n);
    for (i = 0; i < (n - 1); i++) {
        cin >> temp1 >> temp2;
        temp1--; temp2--;
        map[temp1].push_back(temp2);
        map[temp2].push_back(temp1);
    }

    int k, goal, start, j;
    cin >> k;
    set<int> been;
    queue<int> steps;
    vector<int> last(n);
    for (i = 0; i < k; i++) {
        cin >> start >> goal;
        start--; goal--;
        last[start] = -1;

        been.clear();
        been.insert(start);
        steps.push(start);

        int node;
        while (steps.size() > 0) {
            node = steps.front();
            steps.pop();
            for (j = 0; j < map[node].size(); j++) {
                if (!been.count(map[node][j])) {
                    steps.push(map[node][j]);
                    last[map[node][j]] = node;
                }
            }
            been.insert(node);
        }

        bool correct = false;
        int out = 2;
        while (!correct) {
            node = goal;
            while (node != -1) {
                if (out <= value[node]) {
                    if (out % value[node] == 0 || (out > 2 && out % 2 == 0)) {
                        correct = false;
                        break;
                    }
                    correct = true;
                    node = last[node];
                }
                else {
                    break;
                }
            }
            if (correct) {
                break;
            }
            out++;
        }

        cout << out << "\n";
    }
}

//9
//7 25 8 4 1000000 6 11 3 2
//5 7
//5 1
//5 6
//7 3
//1 2
//1 4
//6 8
//2 9
//3
//8 9
//3 8
//4 9