Under the command of the Evil Vizier there are N unique troops of sand monsters, where each  troop contains Ci sand monsters. The Vizier in his desperate battle against the Prince of Persia has ordered all his troops to attack him simultaneously.
 
The Prince realizes that he cannot defeat all of the sand monsters, as they are invincible  when they are active. So he uses the Eye of the Storm spell to freeze all the sand monsters of all troops. Now the Prince can kill any monster by stabbing each monster once using the Dagger of Time. Once the monster is killed, it can never become active again and releases a certain quantity of the Sands of Time. It takes one unit of time to kill any monster.
 
Each troop i, consits of Ci similar monsters, all with the same spell resistance time Ti - after which it becomes active again and therefore invulnerable - and Sand Si - which can be taken by the Prince after killing it.
 
The spell lasts only for a limited duration of time. So, the Prince has to kill as many sand monsters as possible and take maximum sand from the monsters before they become active again. It is not necessary for The Prince to kill all the monsters in a troop before moving on to next troop.

Input

The first line contains K <=70  the number of testcases. Each testcase begins with 'N' (<=1000) the number of troops of monsters. Next N lines contain 3 integers Ci, Ti, Si. 1<i<=N,  1<=Ci<=15000, 1<=Ti<=1000000, 1<=Si<=100,

Output

Single Line containing the maximum amount of sand that Prince can get if he kills some or all the monsters.

Example

Input:
1 
4 
2 1 2 
2 3 6 
2 5 5 
2 7 8

Output:
40

Explanation
(time, troop, sand) 
(0,1,2) (1,2,6) (2,2,6) (3,3,5) (4,3,5) (5,4,8) (5,4,8) = 40