As you might be knowing, Blackhood, Kira and BaZ are very good friends. They are gonna meet after a long time (not that long though :p).They live in a country consisting of N cities . Each city has a GDP (not necessary distinct). The roads of the country are such that there is only one road connecting any two cities in the country. Kira and Blackhood decide to meet anywhere in the unique path between their cities (including their cities too). But BaZ is not ready to meet anywhere, since he likes numbers having at least K distinct prime factors, he agrees to meet only in those cities whose GDP is a number he likes. Given Blackhood's and Kira's home cities, you need to find the number of cities where they can meet. i.e. you need to tell the number of cities between Blackhood's and Kira's home city which have their GDP a number BaZ likes.

Input

First line of the input contains three integers N, representing the number of cities in the country, K (as explained above) and Q, the number of queries which are to be answered). (1<=N, Q<=200000, 0<=K<=100). Next line contains N integers, where the ith integer represents the GDP of the ith country (1<=GDP[i]<=1000000). The next N-1 lines contain two integers u and v, representing a road between city u and city v (1<=u, v<=N). Then the Q following lines contain two integers u and v, representing Blackhood's and Kira's home cities.

Output

For each query, output an integer representing the number of cities where the three can meet.

Note: Large input data, use FAST I/O. Be careful with certain languages too.

Example

Input:
5 2 5 
10 1 6 9 14 
1 2 
2 4 
1 3 
3 5 
1 2 
4 5 
2 3 
2 5 
3 5 

Output:
1
3
2
3
2