Дано дерево (неориентированный связный граф без циклов), состоящее из $N$ вершин. Вершины пронумерованы от $1$ до $N$, рёбра — от $1$ до $N-1$. Каждая вершина имеет вес.

Напишите программу, которая выполняет следующие запросы:

• u v: вывести количество различных весов вершин на пути от $u$ до $v$.

Входные данные

В первой строке задано $N$ ($2 \le N \le 100\,000$).

Во второй строке перечислены веса вершин в порядке от вершины $1$ до вершины $N$.

В следующих $N-1$ строках заданы пары чисел $u$ и $v$ — номера вершин, соединяемых $i$-м ребром.

В следующей строке задано число запросов $M$ ($1 \le M \le 100\,000$).

В следующих $M$ строках заданы запросы, по одному в строке.

Вес каждой вершины — натуральное число, не превосходящее $1\,000\,000$.

Выходные данные

Для каждого запроса в порядке их следования выведите результат в отдельной строке.

Примеры

Входные данные 1

8
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2
2 5
7 8

Выходные данные 1

4
4