WPAIRPRIME

Submit solution
Points: 6
Time limit: 1.0s
Memory limit: 512M
Problem type

Cho số nguyên dương \(N\) và dãy số nguyên \(A_1,A_2,..,A_N\). Cho \(Q\) truy vẫn, mỗi truy vấn mô tả bới \(2\) số nguyên \(L\) và \(R\). Với mỗi truy vấn , tính số lượng cặp \((i,j)\) sao cho: \(L ≤ i < j ≤ R\) và \(A_i+A_j\) có thể được biểu diễn dưới dạng tổng của một hoặc nhiều số nguyên tố. Trong tổng này, có thể sử dụng một số nguyên tố nhiều hơn một lần.

Input:

  • Dòng đầu tiên chứ số nguyên \(T (1 ≤ T ≤ 10)\) – là số bộ Test, với mỗi bộ Test

    • Dòng 1: chứa hai số nguyên \(N (2 ≤ N ≤ 10^5 \));

    • Dòng 2: chứa \(N\) số nguyên \(A_1,A_2,…,A_N\) (\(0 ≤ A_i ≤ 10^5\) );

    • Dòng 3: chứa số nguyên \(Q\) (\(1 ≤ Q ≤ 10^5\) );

    • \(Q\) dòng tiếp theo, mỗi dòng chứa \(2\) số nguyên \(L,R (1 ≤ L < R ≤ N)\).

Output:

  • Đối với mỗi truy vấn, in ra số lượng cặp thỏa mãn các điều kiện đã cho, kết quả mỗi test in trên một dòng riêng biệt.

Sample Input

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

Sample Output

2
9

Ràng buộc

  • Subtask 1: \(N ≤ 1000\)

  • Subtask 2: \(N ≤ 10^5\)

Comments