BARB - Barbarians

no tags 

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.

Please note that this problem has a somewhat strict source limit and time limit.

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

 Year  Barbarian 1  Barbarian 2  Barbarian 3 
0123
1435
214Died
345Died
41DiedDied


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:1s
Source limit:2048B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 2002,Day 2; translated by Blue Mary