Pyramid

The key parameters of the “gradual square pyramid” from the figures are stair depth (x) and stair height (y). Given the (x₁,y₁), (x₂,y₂), …, (x_n,y_n) pair sequence (n ≤ 20; x_i < 100, y_i < 10, i=1, …,n), find out the optimal succession that minimize the volume of the pyramid.

Input Specification

The first line of the input contains the number of the given test cases, after which each line contains a test case: the value of n, followed by pairs of integers representing the stair height and depth, separated by white characters: n y₁ x₁ y₂ x₂ … y_n x_n.

Output Specification

A line for each test case written to the standard output: the indexes of the height-depth pairs in the correct order, separated by spaces.

Sample Input

1. 1
2. 6 3 10 2 11 1 5 3 11 2 5 1 10

download as text file

Output for Sample Input

1. 5 1 4 3 2 6

download as text file