An và Bình đang chơi một trò chơi. Đầu tiên, An cho một dãy số nguyên ~A~ có ~N~ phần tử được đánh số từ ~1~ đến ~N~. Sau đó, An cho tiếp ~Q~ truy vấn, mỗi truy vấn là một bộ ba số ~X, L, R~.

Một truy vấn được xem là hợp lệ nếu tích ~A_L \times A_{L+1} \times \dots \times A_R~ chia hết cho ~X~. An đố Bình có bao nhiêu truy vấn hợp lệ trong số ~Q~ truy vấn đã cho.

Yêu cầu: Bạn hãy giúp Bình trả lời câu hỏi của An về số lượng truy vấn hợp lệ.

Input

• Dòng đầu chứa số nguyên ~N~ ~(1 \le N \le 10^5)~ là số phần tử của dãy ~A~;

• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(0 \le A_i \le 1000; 1 \le i \le N)~ biểu thị dãy số ~A~, các số cách nhau bởi dấu cách;

• Dòng thứ ba chứa số nguyên ~Q~ ~(1 \le Q \le 10^5)~ là số lượng truy vấn;

• Trong ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa ~3~ số nguyên ~X_i, L_i, R_i~ ~(1 \le X_i \le 10^9; 1 \le L_i \le R_i \le N; 1 \le i \le Q)~ như mô tả ở trên.

Output

Ghi ra một số nguyên cho biết số lượng truy vấn hợp lệ.

Scoring

Sample Input 1

5
1 5 3 4 0
3
4 1 2
5 3 5
12 1 4

Sample Output 1

2

Notes

• Truy vấn ~1~: tích ~1 \times 5 = 5~ không chia hết cho ~4~.

• Truy vấn ~2~: tích ~3 \times 4 \times 0 = 0~ chia hết cho ~5~.

• Truy vấn ~3~: tích ~1 \times 5 \times 3 \times 4 = 60~ chia hết cho ~12~.

Vì vậy, có ~2~ truy vấn hợp lệ.