Too lazy for a story, let's jump into the question directly.

Given an array $A$ of size $N$, and $Q$ queries. In each query you are given two integers $L$ and $R$. For each query find the product of number of even elements and number of odd elements from $A[L]$ to $A[R]$ (Both inclusive). 

NOTE: This Question contains heavy I/O. 

Input Format:

First line contains $T$, the number of test cases.

First line of each test case contains two integers $N$ and $Q$, the size of the array and the number of queries respectively.

Second line of each testcase contains $N$ space separated integers (the array $A$).

Next $Q$ lines of each testcase contains two integers $L$ and $R$ (0 - based), the start and end index respectively.

Output Format:

For each query (in all the testcases) print the required result.

Constraints:

1 <= $T$ <= 10

1 <= $N,Q$ <= 100000

0 <= $L,R$ < $N$

0 <= $A[i]$ <= 1000