# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

You are given a rooted tree (a connected graph with no cycles) with n vertices. The vertices are numbered from 1 to **n**, the root is
the vertex number **1**. Each vertex i has an integer color **C**_{i}.

In this problem, you need to answer **q** queries. Each query we will ask you to perform the following operation:**u v** : ask for how many numbers are divisible by **3** from common vertices between **Subtree-u and Subtree-v**.

Subtree of a node is a part of tree consisting of this node and all it’s descendants (direct or not). In other words, subtree of node p is formed by nodes s, such that node p is present on the path from s to root.

The first line contains a single integer **n (2 ≤ n ≤ 10 ^{5})** — the number of vertices in the tree.
Each of next n lines contains a single integer color. The

The next **n-1** lines contain the edges of the tree. The **i ^{th}** line contains the numbers

The next line contains a single integer

Each of next

Print **q** integers — the answers to the queries in the order the queries appear in the input

Input | Output |
---|---|

3 3 5 9 1 2 3 1 2 1 3 2 2 | 1 0 |