Do you remember the game of Snakes and Ladders ? We have removed all the snakes from the board. However to compensate for the loss of trouble, we have enlarged the board from a maximum limit (Target Square) of 100 to a maximum limit (Target Square) of N>=100, N being a perfect square.

Rani has a match with Nandu on this new kind of board next week.

Now Rani is practising alone on the board. Suddenly Rani starts wondering : "Suppose I have total control over both my dice (each die being a standard 1-6 die) and I am the only player playing all the turns such that in each turn I throw both the dice, what is the minimum number of turns in which I can reach the Target Square N ? "

Given the configuration of the board ie. given all the information about the location of Ladders on the board, find the answer to Rani's question.

Note (to player) :

• You start from Square Number 1.
• If you reach a square which contains the base of a ladder, you have to climb up that ladder in the same turn itself (it is compulsory to climb the ladder). Note that you can only climb up ladders, not climb down.
• Say you are at square number N-2. The only way you can complete the game is by getting a 2 by throwing both your dice. If you throw a 4 or a 5 or anything else, your turn goes wasted.

Input :

First line consisits of T denoting the number of test cases. The first line of each test case consists of 2 space-separated integers N an L denoting the Target Square and number of ladders respectively. The next L lines are such that each line consists of 2-space separated integers B and U denoting the squares where the bottom and upper parts of each ladder lie.

Ouptut:

Print a single integer per test case on a new line, the answer to Rani's question.

Constraints :

1<=T<=3

100<=N<=160000, N being a perfect square

0<=L<=SquareRoot(N)

1<=B<U<=N

Author : Shreyans

Tester : Sandeep

(By IIT Kgp HackerEarth Programming Club)