Description

Little X, who lives on a 2D plane, is preparing to visit Little Y. However, due to climate changes, a monsoon has started blowing across the plane. Little X wants to know the minimum number of days it will take to reach Little Y's home under the influence of the monsoon. Since this is the first time Little X has encountered such a strange phenomenon, please help them out using your algorithmic expertise.

Given $n, k, x, y$ and $2n$ integers $x_0, y_0, x_1, y_1, \dots, x_{n-1}, y_{n-1}$. Find the minimum non-negative integer $m$ such that there exist $2m$ real numbers $x'_0, y'_0, x'_1, y'_1, \dots, x'_{m-1}, y'_{m-1}$ satisfying the following conditions, or report that no such $m$ exists:

• $\sum_{i=0}^{m-1} (x'_i + x_{i \pmod n}) = x$;
• $\sum_{i=0}^{m-1} (y'_i + y_{i \pmod n}) = y$;
• $\forall 0 \le i \le m - 1, |x'_i| + |y'_i| \le k$.

Specifically, when $m=0$, both $\sum_{i=0}^{m-1} (x'_i + x_{i \pmod n})$ and $\sum_{i=0}^{m-1} (y'_i + y_{i \pmod n})$ are considered to be $0$.

Input

The first line contains an integer $T$, representing the number of test cases. For each test case: The first line contains four integers $n, k, x, y$. The next $n$ lines each contain two integers $x_{i-1}, y_{i-1}$.

Output

For each test case, output a single integer on a new line. If there exists an $m$ satisfying the conditions, output the minimum possible value; otherwise, output $-1$.

Examples

Input 1

4
1 2 2 2
1 1
1 2 -2 -2
1 1
1 2 0 0
1 1
2 100000000 100000000 100000000
-99999999 0
-100000000 0

Output 1

1
-1
0
399999999

Note

The sample contains four test cases. For the first test case, taking $m=1$ and $(x'_0, y'_0) = (1, 1)$ satisfies the conditions. It can be proven that no smaller $m$ satisfies the conditions. For the second test case, it can be proven that no non-negative integer $m$ satisfies the conditions. * For the third test case, taking $m=0$ satisfies the conditions. It can be proven that no smaller $m$ satisfies the conditions.

Subtasks

Let $\sum n$ be the sum of $n$ over all test cases in a single test file. For all test cases: $1 \le T \le 5 \times 10^4$; $1 \le n \le 10^5$, $1 \le \sum n \le 10^6$; * $0 \le |x|, |y|, |x_i|, |y_i|, k \le 10^8$.

Special Property A: $\forall 0 \le i \le n - 1, |x_i| + |y_i| \le k$. Special Property B: $k = 0$. Special Property C: $x_0 = y_0 = 0$.

Note

The input files for this problem are large; please use fast I/O methods.