Given a sequence A consisting of N integer elements: A₁, A₂, .., A_N.

Your task is to answer Q queries. Each query requires to count the number of pairs of integers (i, j) such that 1 ≤ i ≤ j ≤ N, and L ≤ A_i XOR A_{i + 1} XOR A_{i + 2} XOR ... XOR A_j ≤ R where L and R are given.

Input

The first line is T - the number of test cases. Then T test cases follow.

Each test case consists of Q + 3 lines. The first line is N. The second line contains N integer denoting the sequence A. Then the next line is Q - the number of quries you must answer. The next Q lines, each line consists of two integer L and R.

Output

For each query, print the answer.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 100000
• 1 ≤ A_i ≤ 10⁹
• 1 ≤ Q ≤ 10
• 0 ≤ L ≤ R ≤ 10⁹
• 20% number of tests in which 1 ≤ N ≤ 2000
• 30% number of tests in which 1 ≤ A_i ≤ 1000