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 gifts must be put in this bag to be taken home. Each prize must be taken in its entirety and may not be taken in certain parts. Determine which gifts need to be brought, so that the total value of the gifts brought can be as maximum as possible. You may carry a number of gifts, so that the total weight is still ≤ N kg.

Input

The first line contains the test case T (1 ≤ T ≤ 100), as many as T 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 gift.

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