Red and Green

Suppose, there is an array of $N$ integers. Each index of the array is either red or green. The first index is red, then the following is green, then the very next one is again red, then green again and the pattern will be like this.

You are given m queries and each query contains $p$, $q$ integers. Your task is to find out the number of red and green lie between the range $p$ and $q$ (inclusive).

Input

The first line of the input contains an integer $T$ ($T ≤ 50$) indicates the testcase. Following $T$ lines there will be two integers $n$ ($1 ≤ n ≤ 10^5$), $m$ ($1 ≤ m ≤ 2 \times 10^3$) indicates the size of array and the number of query respectively. The index will be 1, 2, ..., n. Then $m$ lines follows two integers $p$, $q$ ($1 ≤ p ≤ q ≤ 10^5$) respectively.

Output

For each query print two integers $r$ and $g$, the total number of red and green in the range. There is a space between $r$ and $g$ and don't forget to print new line after each query.

Sample

Input	Output
2 5 2 1 3 1 5 10 4 5 5 2 9 4 8 1 10	2 1 3 2 1 0 4 4 2 3 5 5