Mike has a tree with n nodes. On each node u, there is an integer \(c_u\).

A number is interesting if and only if its digits in the decimal representation are distinct. For example, the numbers \(1546,198,1\) are interesting but the numbers \(1222,1001,9011\) are not.

Consider a length-k path on the tree \(P_1,P_2,...,P_k\), a subpath is determined by two parameters l and r (\(1 \le l \le r \le k\)). The subpath starting from \(l^{th}\) node and ending on \(r^{th}\) node is \(P_l,P_{l+1},...,P_r\). Therefore, a length-k path has \(\frac{k \times (k + 1)}{2}\) subpaths.

He has q queries. Each query consists of two numbers, u and v. Considering the path starting from u and ending at v, he wants to know the number of interesting subpaths. A subpath is interesting if and only if there exists at least one node on the subpath whose assigned number is interesting.

Input

The first line contains a number n (\(1 \le n \le 500\,000\)).

The next line contains n numbers \(c_1,c_2,...,c_n\) - \(c_i\) is the assigned number to node i (\(1 \le c_i \le 10^9\)).

The next \(n - 1\) lines contains two numbers separated by space.The \((i+2)^{th}\) line contains \(a_i,b_i\) (\(1 \le a_i , b_i \le n\)) representing that there is an edge from the node \(a_i\) to the node \(b_i\).

The next line contains a number q (\(1 \le q \le 500\,000\)).

The next q lines contains two numbers separated by space.The \((n+1+i)^{th}\) line contains \(u_i,v_i\) (\(1 \le u_i,v_i \le n\)).

Output

Output q lines. The \(i^{th}\) line must contain the answer for the \(i^{th}\) query.