Mamy drzewo (graf spójny bez cykli) złożone z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$, a krawędzie od $1$ do $N-1$. Każdy wierzchołek ma wagę.

Napisz program wykonujący następujące zapytania:

• u v: wypisz liczbę różnych wag wierzchołków na ścieżce od $u$ do $v$.

Wejście

Pierwszy wiersz zawiera $N$ ($2 \le N \le 100\,000$).

Drugi wiersz zawiera wagi wierzchołków w kolejności od wierzchołka 1 do $N$.

Kolejne $N-1$ wierszy zawiera po dwie liczby $u$ i $v$ – numery wierzchołków połączonych $i$-tą krawędzią.

Następny wiersz zawiera liczbę zapytań $M$ ($1 \le M \le 100\,000$).

Kolejne $M$ wierszy zawiera po jednym zapytaniu.

Wagi wierzchołków są zawsze liczbami naturalnymi nie większymi niż $1\,000\,000$.

Wyjście

Dla każdego zapytania, w osobnej linii, wypisz wynik w kolejności wystąpienia.

Przykład

Wejście 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

Wyjście 1

4
4