Mr. Malnar has made a pizza with $n$ peppers, where the coordinates of the $i$-th pepper are $(x_i, y_i)$. We can imagine the pizza as a square from point $(0, 0)$ to point $(m, m)$. He now wants to share this pizza with his friend Ivan.

Mr. Malnar will cut the pizza along a certain line. Additionally, he considers a line to be an integer line if it can be written as $y = ax + b$ where $a$ and $b$ are integers. To share the pizza fairly with Ivan, he needs to choose an integer line such that the number of peppers on both sides of the line is equal, and naturally, the line must not pass through any of the peppers.

To help them, output how many such lines exist, or $-1$ if there are infinitely many.

Input

The first line contains the number $T$ ($1 \le T \le 10^4$). $T$ test cases follow.

In each test case, the first line contains the numbers $n$ and $m$ ($2 \le n \le 10^6$), where $n$ is even, and ($1 \le m \le 10^5$). The next $n$ lines contain the coordinates of the peppers $x_i$ and $y_i$ ($0 \le x_i, y_i < m$).

The sum of $n$ over all test cases is less than or equal to $10^6$, and the sum of $m$ over all test cases is less than or equal to $10^5$.

Output

For each test case, output the number of such lines, or $-1$ if there are infinitely many.

Examples

Input 1

1
2 2
0 1
1 0

Output 1

-1

Input 2

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

Output 2

4

Input 3

1
6 10
0 0
5 0
5 0
4 9
9 9
9 9

Output 3

36