There are N Barbarians living on an unknown island. On the island there are M caves, we can number them 1, 2 ... M clockwise. When we find the island, the barbarians are living in N distinct caves numbered C1, C2 ... CN. Every year each barbarian walks out of his cave and goes along the road, passes Pi caves and then go into that cave. Every Barbarian has a living time: Li years, after Li years the ith barbarian died.

We are surprised to find out that no two barbarians live in one cave in the same year so no conflicts have happened. We are interesting about the minimum number of caves on the island.

Input

The very first line contains a single integer T, the number of test cases. T blocks follow.

For each test case, the first line contains a single integer N (N ≤ 15). N lines follow, each contains 3 integers Ci (1 ≤ Ci ≤ 100), Pi (1 ≤ Pi ≤ 100), Li (1 ≤ Li ≤ 1,000,000).

Output

For each test case, the first and only line contains a single integer M - the answer. You may assume M ≤ 1,000,000.

Example

Input:
1
3
1 3 4
2 7 3
3 2 1

Output:
6

Explanation