Jovians, the citizens of Jupiter, have a very long life, and all the Jovians are a part of one family. Since they have a very long life, in order to control population, all the Jovians are allowed to have at most 2 children and not more.

Every Jovian earns a particular amount of money in his lifetime. Whatever he possess, gets evenly distributed among his children, ie. If there is only 1 child, all the parents money will come to him, else if there are two children, each of them will inherit half of the parents’ income.

Jakhi, the Rakhi Sawant of Jupiter recently organized a Swayamvar, to choose a groom among all the Jovians.

Jakhi being very greedy, wants her husband to be the richest being on the planet.

Help Jakhi to find out the money, that the richest Jovian has.

Input:
First line contains number of test cases. The first line of every test case is N, the total number of Jovians. The next N-1 lines contains three space separated integers A, B and V, where B is the father of A, and V is the amount of money A earned. 0th Jovian is the supreme and all other are his descendants and has earned 50 units .
Output:
A single integer output for every test case.

1<=N<=10000
0 0<=B