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.

The size of the input file does not exceed 0.1 MiB.

Input

The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

Each test case starts with a line containing the number of aliens $n$ ($1 \le n \le 300$). Of the next $n$ lines, the $i$-th one contains three integers $a_i$, $b_i$, $d_i$, ($1 \le a_i < b_i \le 10\,000$; $1 \le d_i \le 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.

Examples

Input 1

1
3
1 4 4
4 7 5
3 4 7

Output 1

7