Một trung tâm khiêu vũ thể thao có \(N\) bạn nam, số hiệu từ \(1\) đến \(N\) và \(M\) bạn nữ, có số hiệu từ \(1\) đến \(M\). Theo đánh giá của Ban huấn luyện trung tâm, bạn nam thứ \(i\ (1\leq i\leq N)\) có chỉ số năng lực là \(b_i\), bạn nữ thứ \(j\ (1\leq j\leq M)\) có chỉ số năng lực là \(g_j\). Và khi ghép cặp thi đấu, nếu ghép bạn nam thứ \(i\) với bạn nữ thứ \(j\) thì cặp thi đấu đó sẽ có chỉ số năng lực bằng tích của chỉ số năng lực của bạn nam và chỉ số năng lực của bạn nữ: \(b_i\times g_j\).

Thời gian đến sẽ có \(Q\) trận thi đấu, Ban huấn luyện của trung tâm đã nghiên cứu và nhận định, trận đấu thứ \(k\ (1\leq k\leq Q)\), để giành phần thắng thì các cặp thi đấu của họ phải có chỉ số năng lực nằm trong khoảng từ \(X_k\) đến \(Y_k\ (X_k\leq Y_k)\). Và họ đã tiến hành ghép và đếm số lượng các cặp thỏa mãn điều kiện cho từng trận đấu.

Yêu cầu: Với mỗi trận đấu bạn hãy tìm xem Ban huấn luyện đã xác định được bao nhiêu cặp thi đấu thỏa mãn điều kiện mà họ đã đặt ra.

Input

• Dòng thứ nhất ghi số nguyên dương \(T\ (1\leq T\leq3)\) là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm:
  • Dòng thứ nhất ghi hai số nguyên dương \(N,\ M\ (N,\ M\geq1)\);
  • Dòng thứ hai ghi \(N\) số nguyên dương \(b_1,\ b_2,\ldots,\ b_N\ (1\leq b_i\leq10^9,\ i=1,2,\ldots,N)\), các số ghi cách nhau bởi dấu cách;
  • Dòng thứ hai ghi \(M\) số nguyên dương \(g_1,\ g_2,\ldots,\ g_M\ (1\leq g_j\leq10^9,\ j=1,2,\ldots,M)\), các số ghi cách nhau bởi dấu cách;
  • Dòng thứ tư ghi số nguyên dương \(Q\) là số trận thi đấu;
  • \(Q\) dòng tiếp theo mỗi dòng mô tả khoảng giới hạn chỉ số năng lực cho một trận đấu, dòng thứ \(k\ (1\leq k\leq Q)\) gồm hai số nguyên dương \(X_k,\ Y_k\ (1\leq X_k\leq Y_k\leq10^{18})\), các số ghi cách nhau bởi dấu cách.

Output

• Dữ liệu ra gồm \(Q\) dòng, mỗi dòng tương ứng với một trận đấu, dòng thứ \(k\ (1\leq k\leq Q)\) ghi một số nguyên dương là số lượng cặp thi đấu thỏa mãn điều kiện tham gia trận đấu thứ \(k\). Lưu ý, kết quả của các bộ dữ liệu ghi ra theo thứ tự tương ứng với thứ tự của dữ liệu vào.

Ví dụ

Sample input

1
4 3
5 1 2 1
6 2 3
3
1 5
6 6
2 30

Sample output

5
3
12

Ràng buộc

• Có \(25\%\) số test ứng với \(25\%\) số điểm của bài có \(N,\ M\leq1000,\ Q\leq80\);
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm của bài có \(N,\ M\leq2500,\ Q\leq1000\);
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm của bài có \(N,\ M\leq40000,\ Q\leq80\);
• Có \(25\%\) số test khác với \(25\%\) số điểm còn lại của bài có \(N,\ M\leq100000,\ Q\leq80\).