Bạn ghuy4g là một người rất giỏi tin, tuy nhiên do sai giới hạn mảng, nên sau một kỳ thi bạn đã không được kết quả như bạn mong muốn. Bạn ghuy4g là một người chăm chỉ và liêm khiết nên thay vì khóc lóc, bạn vẫn luôn cố gắng luyện tập mỗi ngày không ngừng nghỉ.

Bạn ghuy4g nhớ rằng có khi đi thi có một bài như sau: Cho dãy ~N~ phần tử, cùng ~Q~ truy vấn, mỗi truy vấn bao gồm hai số nguyên dương ~L, R~, với ý nghĩa: tính số cặp ~i, j~ (~L \le i, j \le R~) mà ~a_i~ chia hết cho ~a_j~. Vì bài này quá dễ nên bạn ghuy4g nghĩ ra một bài khó hơn.

Cho một cây gồm ~n~ đỉnh. Mỗi đỉnh sẽ được gán một trọng số là ~a_i~. Cho ~q~ truy vấn, mỗi truy vấn là hai đỉnh ~u, v~, yêu cầu đếm số cặp ~i, j~, với ~i, j~ nằm trên đường đi đơn từ ~u~ tới ~v~, mà ~a_i~ chia hết cho ~a_j~.

INPUT

Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~q~ (~1 \le n, q \le 40000~), là số đỉnh của cây và số truy vấn.

Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \le a_i \le 40000~) là các trọng số của các đỉnh.

~n - 1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u~ và ~v~ (~1 \le u \le v \le n~, ~u \neq v~) mô tả một cạnh của cây.

~q~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~u~ và ~v~ (~1 \le u \le v \le n~) mô tả một truy vấn.

OUTPUT

~q~ dòng, mỗi dòng là kết quả của một truy vấn.

SAMPLE INPUT

5 3  
2 6 3 12 4  
1 2  
1 3  
3 4  
3 5  
1 4  
2 5  
3 3  

SAMPLE OUTPUT

5
7
1

SUBTASKS