Юрі дано дерево, що складається з ~n~ вершин, пронумерованих числами від ~1~ до ~n~. На кожній вершині вказаний її колір — натуральне число ~c_i~.

Юру попросили відповісти на ~q~ запитів. Кожен запит складається з двох вершин ~u~ та ~v~. Відповіддю на запит є кількість різних кольорів, які зустрічаються на простому шляху між вершинами ~u~ та ~v~.

Простий шлях — це шлях, в якому кожна вершина та кожне ребро зустрічаються не більше ніж один раз.

Input

У першому рядку розміщене число ~n~ ~(1 \le n \le 10^5)~ — кількість вершин в дереві.

У другому рядку розміщено ~n~ цілих додатніх чисел ~c_i~ ~(1 \le c_i \le min(n, 5000))~ — кольори вершин дерева.

У наступних ~n - 1~ рядках розміщено по два числа ~u~ та ~v~ ~(1 \le u,~ ~v \le n)~ — номери вершин між якими існує ребро.

У наступному рякдку розміщено число ~q~ ~(1 \le q \le 10^5)~ — кількість запитів.

У наступних ~q~ рядках розміщено по два числа ~u~ та ~v~ ~(1 \le u,~ ~v \le n)~ — номери вершин для яких потрібно знайти відповідь.

Output

Виведіть ~q~ цілих чисел — відповіді на запити. Кожна відповідь в новому рядку.

Sample Input 1

5
1 2 3 1 2
1 2
2 3
3 4
4 5
4
1 1
4 2
3 1
5 2

Sample Output 1

1
3
3
3

Sample Input 2

13
1 2 3 4 5 1 2 3 4 5 1 2 3
1 2
1 3
1 13
2 4
2 7
3 6
3 5
4 8
8 9
6 10
5 11
5 12
10
1 13
13 6
10 12
6 11
8 7
4 1
1 10
13 10
8 10
4 12

Sample Output 2

2
2
4
3
3
3
3
3
5
5