Zeta is a lucid dreamer. He uses sedative for lucid dreaming and keeps on making new and effective sedatives. One day he decided to visit the nearby chemical shop and buy some chemicals. He buys exactly N chemicals and decides to make different sedatives from a combination of available chemicals. He arranges the chemicals in a form of tree. Now each chemical has lucidness associated with it.
You are given an array I of size N, where \(I_i\) represents the Chemical ID of \(i^{th}\) chemical. Lucidness of a chemical is defined as “Number of divisors of Chemical ID”.
He decided to make Q sedatives and for each sedative he selects chemicals by starting from a chemical A and going up to chemical B and selecting all the chemicals that come in the path. Now Lucidness of a sedative is “Sum of lucidness of all chemicals”. Zeta labels each sedative with the Lucidness as more lucidness means more stable dreams.
Since Zeta is busy in preparing the sedatives you have to find the value of these labels for him.

Input Format:
First line contains three space separated integers N, M and Q which denote Number of chemicals, Number of edges and Number of sedatives respectively.
Second line contains array I (N space separated non-negative integers), where \(I_i\) denotes Chemical ID of \(i^{th}\) chemical.
Next M lines contain two integers U and V representing an edge between \(U^{th}\) chemical and \(V^{th}\) chemical.
Next Q lines contains A and B

Output Format:
Print Lucidness (as explained above) in new line for every A and B.

INPUT CONSTRAINTS
\(1 \le N,M\le 10^5\)
\(1 \le Q \le 10^6\)
\(0 \le I_i \le 10^7\)
\(1 \le A,B \le N\)