There are crazy savages on a mysterious island. There are m caves arranged in a circle. The caves are numbered 1,2,...m in clockwise order. There are n savages, the i-th savage lived in cave C_i initially, and every day, he leaves the cave in the morning and lives in the P_i-th cave in clockwise direction, and he will be alive only for L_i days.

For example, the 4 figures above show an island with 6 caves and 3 savages. The 3 savages lived in cave 1,2,3, The number of caves they skip every day are 3,7,2, and the number of days they're alive are 4,3,1. Note that the dead savages are not shown in the figures.

Savages like fighting, so if two(even more) of them meet, they will fight to death. But surprisingly enough, the fact is: None of them have met before they die natually! Please tell me the least number of m that will cause the amazing result. There will always be a solution, and m<=1,000,000.

Input

The first line of the input is a single integer t(1<=t<=10), indicating the number of test cases. Each case begins with a line containing a single integer n(1<=n<=15), indicating the number of savages. The next n lines each contain 3 integers: C, P, L(1<=C,P<=100, 0<=L<=1,000,000).

Output

For every test case, print a line containing the value of m, the least number of caves.

Sample Input
2
3
1 3 4
2 7 3
3 2 1
5
1 2 14
4 4 6
8 5 9
11 8 13
16 9 10

Sample Output
6
33