Nandu works in a company that transport rings. For each ring transported by Nandu he gets some coins. He transports rings by fitting one ring into another. A ring fits into another ring if and only if the outer radius of first ring is less than or equal to inner radius of other ring. Nandu want to maximize his coins. So he wants your help to find the maximum possible number of coins he can get.

INPUT

First line contains number of test cases T. Each test case contains number of rings N. Next N line contain IR inner radius of ith ring , OR outer radius of ith ring and C number of coins Nandu gets for ith ring.

OUTPUT

For each test case Print maximum possible number of coins Nandu can get.

Constraints

1<=T<=100
1<=N<=100000
1<=IR<=100000
1<=OR<=100000
1<=C<=100000