After Johnny spent a long day in school, he decided to play a spot game with his friends. A Spot game is played as follows, there are N spots on a horizontal line one after another, each spot i has a radius R[i]. The player may start at any spot, but is only allowed to move from one spot to another if it occurs after it in the line and its radius is greater than the previous one. When he plays a move on a spot i he earns P[i] points. The player wins when he goes through the maximum number of spots if there are multiple ways, He must earn the maximum sum of points, if there are still multiple ways he must select the one that is lexicographically maximal (Let A=(a1,...,aN) and B=(b1,...,bN) be two different but equally large solution, with a1 >= a2 >= ... >= aN and b1 >= b2 >= ... >= bN. Let x be the smallest index such that ax != bx. If ax > bx, we say that the set A is lexicographically larger than the set B). As Johnny is a smart boy he wants to play optimally, so he asked you to show him which spots to move in order to win the game, Can you help him?

Input Format

Input will start with T number of test cases. Each test case starts with N where 1 <= N <= 1500 represent number of spots. Then follow N lines each contains two integers R[i] and P[i] where 1 <= R[i] <= 300 is the radius of i-th spot and 1 <= P[i] <= 2,000,000 is the points earned when you move on i-th spot.

Output Format

For each test case, output the result using the following format:

K (start with 1) followed by a period, and a single space, then print the indices (1-based) of the spots that Johnny visits separated by a single space. If there are more than one subsequence of spots that makes Johnny wins then print the lexicographically largest.

Sample

Input
2
6
1 3
2 3
6 3
4 20
3 15
9 10
6
1 3
1 3
6 3
4 20
3 15
9 10

Output
1. 1 2 4 6
2. 2 4 6