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 Ci initially, and every day, he leaves the cave in the morning and lives in the Pi-th cave in clockwise direction, and he will be alive only for Li 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 134
2/2 273 321 5 1 2 14 446 859 11 8 13 16 9 10 Sample Output 6 33