You are given n closed integer intervals [a_i, b_i] and n integers c₁, ..., c_n.

Task

Write a program that:

Input

The input begins with the integer t, the number of test cases. Then t test cases follow.

For each test case the first line of the input contains an integer n (1 <= n <= 50000) - the number of intervals. The following n lines describe the intervals. Line (i+1) of the input contains three integers a_i, b_i and c_i separated by single spaces and such that 0 < = a_i < = b_i <= 50000 and 1 < = c_i < = b_i -a_i +1.

Output

For each test case the output contains exactly one integer equal to the minimal size of set Z sharing at least c_i elements with interval [a_i, b_i], for each i= 1, 2, ..., n.

Example

Sample input:
1
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

Sample output:
6