Kiana is addicted to a magical game.

Simply put, this game is played on a plane. There is a slingshot located at $(0, 0)$. Each time, Kiana can launch a red bird from the slingshot. The flight trajectory of the bird is a curve defined by $y = ax^2 + bx$, where $a$ and $b$ are parameters specified by Kiana, and it must satisfy $a < 0$.

When the bird hits the ground (the $x$-axis), it disappears instantly.

In a certain level of the game, there are $n$ green pigs in the first quadrant of the plane, where the $i$-th pig is located at $(x_i, y_i)$.

If the flight trajectory of a bird passes through $(x_i, y_i)$, then the $i$-th pig will be eliminated, and the bird will continue to fly along its original trajectory.

If the flight trajectory of a bird does not pass through $(x_i, y_i)$, then the bird's flight will not have any effect on the $i$-th pig.

For example, if two pigs are located at $(1, 3)$ and $(3, 3)$, Kiana can choose to launch a bird with the trajectory $y = -x^2 + 4x$, and both pigs will be eliminated by this bird.

The goal of this game is to eliminate all the pigs by launching birds.

This magical game is very difficult for Kiana, so she has entered some mysterious commands to make it easier to complete the level. These commands are described in the Input section.

Suppose there are $T$ levels in total. Now Kiana wants to know, for each level, what is the minimum number of birds required to eliminate all the pigs. Since she cannot calculate it, she hopes you can tell her.

Input

The input is read from the file angrybirds.in.

The first line contains a positive integer $T$, representing the total number of levels.

The following lines contain information for the $T$ levels. Each level starts with two non-negative integers $n$ and $m$, representing the number of pigs in the current level and the mysterious command entered by Kiana, respectively. The next $n$ lines each contain two positive real numbers $x_i, y_i$, representing the coordinates $(x_i, y_i)$ of the $i$-th pig. It is guaranteed that no two pigs in the same level have the same coordinates.

If $m = 0$, it means Kiana did not enter any special command.

If $m = 1$, this level will satisfy: at most $\lfloor n/3 + 1 \rfloor$ birds are sufficient to eliminate all pigs.

If $m = 2$, this level will satisfy: there must exist an optimal solution where at least one bird eliminates $\lfloor n/3 \rfloor$ pigs.

It is guaranteed that $1 \le n \le 18$, $0 \le m \le 2$, $0 < x_i, y_i < 10$, and all real numbers in the input are given to two decimal places.

In the text above, the symbols $\lceil c \rceil$ and $\lfloor c \rfloor$ represent the ceiling and floor of $c$, respectively. For example, $\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$.

Output

Output to the file angrybirds.out.

For each level, output the answer on a new line.

Each line of the output contains a positive integer, representing the minimum number of birds required to eliminate all pigs in the corresponding level.

Examples

Input 1

2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

Output 1

1
1

Note 1

This set of data contains two levels.

In the first level, which is the same as the scenario in the description, two pigs are located at $(1.00, 3.00)$ and $(3.00, 3.00)$. Launching a bird with the trajectory $y = -x^2 + 4x$ is sufficient to eliminate them.

In the second level, there are 5 pigs. By observation, we can find that their coordinates all lie on the parabola $y = -x^2 + 6x$, so Kiana only needs to launch one bird to eliminate all the pigs.

Input 2

3
2 0
1.41 2.00
1.73 3.00
3 0
1.11 1.41
2.34 1.79
2.98 1.49
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00

Output 2

2
2
3

Input 3

1
10 0
7.16 6.28
2.02 0.38
8.33 7.78
7.68 2.09
7.46 7.86
5.77 7.44
8.24 6.72
4.42 5.11
5.42 7.79
8.15 4.99

Output 3

6

Subtasks

Some special constraints on the data are as follows: