Misère
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Préférence is a card game which is very popular in Eastern Europe. It is usually played with a 32-card deck, which consists of pip cards from 7 to 10, Jack, Queen, King, and Ace in each of the four suits: Spades, Clubs, Diamonds, and Hearts. In each round of the game, three players receive ten cards each, and two cards are left on the table as a talon. Then, a phase of auction happens, where players make their bids, which are obligations to take at least a certain number of tricks. A special case of a bid is a so-called misère, which is an obligation to take no tricks regardless of other players' moves.

In this task, we will consider a special modification of préférence which is played with a modified deck containing $$$A\cdot B$$$ cards, where $$$A$$$ is a number of suits, and $$$B$$$ is the number of ranks in each suit. For example, the standard 32-card deck for the préférence game has $$$A = 4$$$ suits and $$$B = 8$$$ ranks. For convenience, we'll number the suits from $$$1$$$ to $$$A$$$, and the ranks from $$$1$$$ to $$$B$$$.

You need to solve a puzzle about this modification of préférence. In this modification, we'll say that a misère is guaranteed if for every suit, after we order the cards belonging to this suit in your hand by their rank as $$$b_1 < b_2 < \cdots < b_k$$$ (where $$$k$$$ is the number of cards of the suit in your hand), the following condition is satisfied: $$$b_i \le 2i - 1$$$ for all $$$i$$$ from $$$1$$$ to $$$k$$$. If you don't have any cards of the suit ($$$k = 0$$$), the condition is trivially satisfied.

You have $$$n$$$ cards in your hand, and you will be allowed to choose any $$$x$$$ cards you don't have and add them to your hand. Then, you must select any $$$x$$$ of your $$$n + x$$$ cards and drop them, leaving some $$$n$$$ cards in your hand. Your task is to find the smallest possible $$$x$$$ such that you can transform your hand to a guaranteed misère.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$A$$$, and $$$B$$$, denoting the number of cards in your hand, the number of suits in the deck, and the number of ranks in the deck ($$$1 \le n \le 5000$$$; $$$1\le A, B\le 10^9$$$).

The $$$i$$$-th of the following $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ and describes one card, where $$$a_i$$$ is the suit of the $$$i$$$-th card, and $$$b_i$$$ is its rank ($$$1 \le a_i \le A$$$; $$$1 \le b_i \le B$$$). All the cards in your hand are distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, print the smallest non-negative integer value of $$$x$$$ such that you can transform your hand to a guaranteed misère by first adding $$$x$$$ cards that you don't have to your hand, and then dropping any $$$x$$$ cards from your hand.

It can be shown that such a value of $$$x$$$ always exists.

Example

Input
2
4 2 6
1 1
1 2
1 6
2 3
2 4 5
3 4
2 4
Output
1
2