You are an owner of a candy factory. In each day, you have to pack J jelly beans into boxes for transfer to the stores.
You have some boxes which may be different in dimension. For your convenience, you want to use least boxes as possible. (You do not need to fill up the box, partly fill is acceptable.)
Write a program that get a number of jelly beans you receive from the factory and dimension of each box and find the number of least boxes can be used. We guarantee that there will be sufficient spaces for the jelly beans.
First line has a number T (1 ≤ T ≤ 10) represent number of test cases. Each test case has a format as follow.
First line has two numbers, J and N (1 ≤ J, N ≤ 1,000) represent number of jelly beans you receive from the factory and number of boxes you have.
For next N lines, each line has two numbers Ri and Ci (1 ≤ Ri, Ci ≤ 10,000) represent dimension (number of rows and columns) of i-th box (There can be two boxes with the same dimension.) This box can be packed with no more than Ri * Ci jelly beans.
Your output should have T lines. Each line represent the number of least boxes can be used in i-th test case.