Don has a rooted tree, consisting of N vertexes. Each tree vertex has a unique index (integer from 1 to N), and also has a unique value associated to it.
The root of Don's tree has index 1.
Also Don has Q pairs of integers: X and Y. For each pair X, Y Don wants to know the Yth largest value in the path from root to Xth vertex.Let this value be P. Finally,Don asks you to calculate S such that
S=f( (( P%100)+1)*2131669703889824641) ,where f(x) is number of divisors of x.
Your task is to write a program that answer the queries asked by Don.
First line contains an integer representing N the number of vertexes. Next line contain n integers ,each representing the value(Ai) associated with each vertex from 1 to N. Next N - 1 lines contain two integers U and V each, which means that vertex U and V are connected to each other. Next line contains an integer Q, the number of Queries. Next Q lines contain 2 integers X and Y each as described in the problem statement. All X will be distinct
For each query print the value of S in a new line
If Yth largest value does not exist then print -1 only in a new line.