Hotels

The city of Leiden draws more tourists every year. Across the street from the Hilbert Hotel near the city border, a competing chain is building a hotel under the project name Lodgings In A Colossal Skyscraper (LIACS). The Hilbert Hotel has infinitely many rooms, and its guests keep complaining that reaching a room takes forever, so the competing chain decided that LIACS will have only finitely many rooms. LIACS is still a colossal skyscraper with $F$ floors.

Floors are connected by elevators and by stairs. Fire regulations require the ground floor to be reachable by stairs alone, so one stairway runs from the top floor down to the ground floor with a door on every floor in between. An elevator fills up once it picks up people on too many floors, so the project manager decided that no elevator stops on every floor. Elevator $i$ stops only on the floors whose number leaves remainder $R_i$ when divided by $M_i$.

Guests do not mind riding an elevator or changing elevators many times in a row, but they dislike stairs. Walking between two adjacent floors counts as one flight of stairs. Guests always enter the hotel on the ground floor, and they may alternate stairs and elevators, because not every elevator stops on the ground floor.

Compute how many flights of stairs a guest has to take to reach a room on the worst possible floor.

The first line has one integer $T$, the number of test cases ($1 \le T \le 50$). Each test case has the following form.

• One line with two integers $F$ and $E$ separated by a space, the number of floors and the number of elevators, with $2 \le F \le 10^9$ and $0 \le E \le 100$. Floors are numbered from $0$ to $F-1$, where $0$ is the ground floor and $F-1$ is the top floor.
• $E$ lines, each with two integers $R_i$ and $M_i$ separated by a space, with $2 \le M_i \le F$ and $0 \le R_i < M_i$. Every elevator stops on at least 1 and at most 1000 floors.

For each test case print one line with two integers $S$ and $W$ separated by a single space.

• $S$ is the smallest number of flights of stairs a guest needs when the room is on the worst possible floor.
• $W$ is the number of that worst floor. If several floors are equally bad, print the one closest to the ground floor.

Take a hotel with 21 floors and two elevators, one stopping on the floors with remainder 0 modulo 3 and one on the floors with remainder 1 modulo 3. The top floor is floor 20. The nearest stop below it is floor 19, and the elevator serving floor 19 does not stop on the ground floor, so a guest staying on floor 20 walks at least two flights of stairs. Add a third elevator stopping on the floors with remainder 2 modulo 3, and a guest can ride from the ground floor to floor 3, walk down one flight to floor 2, then ride to floor 20. One flight of stairs is then enough for every room.