You are given a tree of N nodes where each node is associated with a value. You are also given a function $F(x)$ whose pseudocode is given below:

function F(int x):
  int ans = 0
  while x > 0:
    ans = ans + (x % 10)
    x = x / 10
  return ans

You will be given Q queries in the format X U V. Here, X is a positive integer while U and V are two nodes of the tree. For each query, you need to find $\sum{F(X + A_i)}$ for all the values $A_i$ on the path from U to V inclusive.

The first line of the input will be a single integer T (1 ≤ T ≤ 10) denoting the number of test cases.

Each test case starts with a line containing a single integer N (2 ≤ N ≤ 10⁵) which is the number of nodes in the tree. Next line of the input will contain N space separated integers A_i (1 ≤ A_i ≤ 10⁹ and 1 ≤ i ≤ N) which are the associated values of the nodes. Next N-1 lines contain two integers U and V (U != V and 1 ≤ U, V ≤ N) denoting there is a bidirectional edge between node U and V. The next line of the input contains Q (1 ≤ Q ≤ 10⁵), the number of queries and next Q lines will contain one query in the form of X U V (1 ≤ X ≤ 10⁹ and 1 ≤ U, V ≤ N). Here X is an integer while U and V are nodes from the tree. It is guaranteed that the sum of N over all test cases doesn’t exceed 10⁵ as well as the sum of Q over all test cases doesn’t exceed 10⁵.

Input file is large. Please be sure to use faster input/output methods.

The first line of each test case should contain the case number in the format: “Case Z:” where Z is the test case number. Then you should print Q lines, one for each query containing the answer. For more clarity, please take a look at the sample IO.

Contest: NCPC 2023 Onsite Hosted by JU

Problem setter: Raihat Zaman Neloy