Problem L
Outer Space Invaders

The aliens from outer space have (finally!) invaded Earth. Defend yourself, or be disintegrated! Or assimilated. Or eaten. We are not yet sure.

The aliens follow a known attack pattern. There are n attackers, the $i$-th one appears at time $a_ i$, at distance $d_ i$ from you. He must be destroyed no later than at time $b_ i$, or else he will fire his weapon, which will definitely end the fight.

Your weapon is an area-blaster, which can be set to any given power. If fired with power $R$, it momentarily destroys all aliens at distance $R$ or smaller. It also consumes $R$ fuel cells.

Determine the minimal cost (measured in fuel cells) of destroying all the aliens, without being killed.

Input

The first line of input contains the number of test cases $T$ ($1 \leq T \leq 5$). The descriptions of the test cases follow:

Each test case starts with a line containing the number of aliens $n$ ($1 \leq n \leq 300$). Of the next $n$ lines, the $i$-th one contains three integers $a_ i$, $b_ i$, $d_ i$, ($1 \leq a_ i < b_ i \leq 10\, 000$; $1 \leq d_ i \leq 10\, 000$). The $i$-th alien appears at time $a_ i$, is idle until $b_ i$, and his distance from you is $d_ i$.

Output

For each test case, output one line containing the minimum number of cells needed to destroy all the aliens.

1
3
1 4 4
4 7 5
3 4 7

7