Cho dãy \(a\) gồm \(n\) số nguyên.

Bạn phải trả lời \(q\) truy vấn, mỗi truy vấn cho hai số nguyên \(b,c\), bạn cần tìm số cặp \((i,j)\) thoả mãn:

• \(1 \le i < j \le n\).
• \(a_i + a_j = b\).
• \(a_i \times a_j = c\).

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) (\(1 \le n \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,...,a_n\) (\(1 \le |a_i| \le 10^9\)).
• Dòng thứ ba chứa một số nguyên dương \(q\) (\(1 \le q \le 2 \times 10^5\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(b,c\) mô tả một truy vấn (\(1 \le |b| \le 2 \times 10^9, 1 \le |c| \le 10^{18}\)).

Output

• Với mỗi truy vấn, đưa ra trên một dòng một số nguyên là kết quả của truy vấn đó.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 10^3, q = 1\).
• Subtask \(2\) (\(20\%\) số điểm): \(|a_i| \le 10^6, |c| \le 10^9\).
• Subtask \(3\) (\(20\%\) số điểm): \(|c| \le 10^9\).
• Subtask \(4\) (\(20\%\) số điểm): \(a_i\) phân biệt từng đôi một.
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

3
1 3 2
1
3 2

1