As the winner of the competition, you are asked to take prizes that are numbered from 1 to K. Each i-prize weighs Wi kg and is worth Hi dollar. You are carrying a bag with a capacity of N kg. The prizes must be put in this bag to be taken home. Each prize must be taken in its entirety and may not be taken in parts. Determine which prizes need to be taken, so that the total value of the prizes can be a high as possible. You may carry a number of prizes, so that the total weight is still ≤ N kg.

Input

The first line contains the number of test cases T (1 ≤ T ≤ 100).,The next line contains two integers separated by spaces, namely N and K.

The next K line contains two Wi and Hi numbers, which represent a description of a prize.

Output

Print the serial number of the prizes so that the total value is maximum. Print these numbers in order from small to large.

If there is more than one optimal prize picking method, print out a method for picking prizes that minimizes weight.

If there is more than one method, prioritize the prizes with the smaller number.

Constraints

1 ≤ N ≤ 2,000

1 ≤ K ≤ 100

1 ≤ Wi, Hi ≤ 2,000, for 1 ≤ i ≤ K

Example

Input:
2
5 3
9 3
10 2
32 2
11 3
10 30
6 17
5 14

Output:
Case 1:
0
Case 2:
2
3