Q10026: Shoemaker's Problem

鞋匠有N件工作要完成。他每天只能做一件工作。並且他知道這些工作分別要幾個工作天才能完成。另外，他也知道每個工作被延誤一天所需被罰的罰金。延誤的天數為從今天算起到該工作開始的那天（所以只有第一件工作沒有罰金）。

以第一組測試資料為例說明：若工作的順序是1 2 3 4，那罰金為：0*4+1000*3+4*2+6*5=3038。若工作的順序是2 1 3 4，則罰金為：0*1000+1*4+4*2+6*5=42。所以第二種工作順序的罰金較少（事實上也是最少）。

你的任務是寫一個程式幫助鞋匠找出完成這N個工作的先後順序，使得罰金最少。

Input

輸入的第一列有一個整數代表以下有幾組測試資料。

每組測試資料的第一列，含有一個整數N（1 <= N <=1000），代表鞋匠需完成的工作數。接下來的N列每列有2個整數，分別代表該工作完成所需的天數以及延遲一天的罰金多少（均大於等於1,小於等於1000）。

第一列和第一組測試資料間，以及各組測試資料間均有一空白列。請參考Sample Inout。

Output

對每組測試資料輸出一列，為這N個工作的順序使得罰金最少。工作之間以一空白字元分隔。如果有不只一組答案，請輸出字典順序最小的那組。

各組測試資料間亦請輸出一空白列。請參考Sample Outout。