Nobita đang ngồi làm bài tập ở nhà, nhưng được một lát cậu ta lại chán chỉ muốn đi ngủ. Doraemon thấy vậy liền nảy ra một ý tưởng để giúp Nobita phấn chấn hơn - đó là đưa Nobita đến vùng đất táo đỏ thần kỳ về hạnh phúc. Khi đến nơi, Nobita choáng ngợp với một cánh đồng mênh mông chỉ toàn táo màu đỏ. Doraemon dẫn Nobita đến trước một cây táo khổng lồ và nói với Nobita rằng đây là cây táo tình yêu; nếu ăn được một cặp táo hợp nhau trên cây thì tình cảm giữa hai người ăn táo sẽ trở nên khăn khít hơn.

Để dễ tưởng tượng, cây táo được biểu diễn dưới dạng một đồ thị dạng cây với mỗi đỉnh đại diện cho một quả táo, cây gồm ~n~ đỉnh được đánh số từ ~1, 2, 3, \dots, n~ và ~n-1~ cạnh. Mỗi quả của cây đều có một chỉ số hạnh phúc, tương ứng ~a_1, a_2, a_3, \dots, a_n~ lần lượt là chỉ số hạnh phúc của các đỉnh từ ~1~ đến ~n~.

Ta định nghĩa một số ~x~ được gọi là số siêu hạnh phúc bậc ~k~ nếu số đó có căn bậc ~k~ là một số tự nhiên (Hay nói cách khác: Số đó có thể biểu diễn dưới dạng ~x^k~ với ~x~ là một số tự nhiên). Ta gọi một cặp quả táo được gọi là hợp nhau nếu tích của 2 chỉ số hạnh phúc của 2 quả táo đó là số siêu hạnh phúc.

Nobita quyết định sử dụng tài năng bắn súng của mình, nhưng cậu chỉ có khả năng bắn rơi tất cả các trái táo nằm trên một đường đi đơn bất kì trên cây. Cậu có ~q~ câu hỏi như sau: Nếu gọi ~S~ là tập các quả táo thuộc đường đi đơn từ ~u~ đến ~v~, thì sẽ có bao nhiêu cặp quả táo ~(a, b)~ sao cho ~a~ và ~b~ đều thuộc ~S~, ~a < b~ và cặp ~(a, b)~ hợp nhau bậc ~k~.

Yêu cầu: Giải đáp các câu hỏi của Nobita.

Input

• Dòng đầu chứa ba số nguyên: ~n, q, k~ (~1 \le n, q \le 10^5~, ~1 \le k \le 5~).
• Dòng tiếp theo là dãy số nguyên dương ~a_1, a_2, a_3, \dots, a_n~ (~1 \le a_i \le 10^6~).
• ~n-1~ dòng tiếp theo lần lượt là các cạnh của đồ thị.
• Tiếp theo là ~q~ dòng chứa các câu hỏi của Nobita, mỗi câu hỏi có dạng ~(u, v)~ với ~1 \le u, v \le n~.

Output

• Ghi ra ~q~ dòng, tương ứng với kết quả của các câu hỏi.

Sample Input 1

6 3 4
1 15 30 7 49 10
1 4
4 2
4 3
4 5
6 5
4 5
1 6
2 4
1 1

Sample Output 1

1
1
0
0