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 Ci.
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.
Input
The first line contains a single integer n (2 ≤ n ≤ 105) — the number of vertices in the tree.
Each of next n lines contains a single integer color. The ith line contains the integer color
Ci(1 ≤ Ci≤ 109) of ith node.
The next n-1 lines contain the edges of the tree. The ith line contains the numbers ai,bi (1 ≤ ai, bi≤ n; ai ≠ bi) — the vertices connected by an edge of the tree.
The next line contains a single integer q— the number of queries.
Each of next q lines contains two integers u, v (1 ≤ u, v ≤ n)
Output
Print q integers — the answers to the queries in the order the queries appear in the input
Sample
| Input | Output |
|---|---|
3 3 5 9 1 2 3 1 2 1 3 2 2 | 1 0 |
