You are given an array \(A\) of length \(N\) and \(Q\) queries. Each query is described by two integers \(L\) and \(R\). For each query, find the number of tuples \((i, j, k)\) such that \(L \leq i \lt j \lt k \leq R\) and \(A[i] + A[j] + A[k]\) is an odd number.

Input Format

First line contains an integer \(T\), which denotes the number of test cases.
The first line of each test case contains two integers \(N\) and \(Q\).
The second line of each test case contains \(N\) space-separated integers, the elements of the array \(A\).
Next \(Q\) lines contain two space separated integers \(L\) and \(R\).

Output Format

For each test case, print an array of length \(Q\), \(i^{th}\) element will be the answer for the \(i^{th}\) query - the number of tuples \((i, j, k)\) such that \(L \leq i \lt j \lt k \leq R\) and \(A[i] + A[j] + A[k]\) is an odd number.

Constraints

\(1 \leq T \leq 10 \\ 1 \leq N, Q, A[i] \leq 10^5 \\ 1 \leq L \leq R \leq N\)