Cho các tập số nguyên ~S_i = \{p: a_i \le p \le b_i\}~ với ~p~ là số nguyên và ~n~ số nguyên ~c_1, c_2, \ldots, c_n~.

Lập trình tìm tập các số nguyên ~Z~ với lực lượng nhỏ nhất sao cho:~|Z \cap S_i| \geq c_i, \forall i \in 1..n~.

Input

Dòng đầu tiên chứa số nguyên dương ~T~ là số testcase thỏa ~1 \le T \le 10~. Mỗi testcase gồm:

Dòng đầu tiên chứa số nguyên dương ~n~ thỏa ~1 \le n \le 50000~.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa các số ~a_i, b_i, c_i~ thỏa ~0 \le a_i \le b_i \le 50000; 1\le c_i \le b_i -a_i+1~.

Output

Ứng với mỗi testcase in ra một số nguyên là lực lượng của tập ~Z~ tìm được, mỗi test in trên một dòng.

Samples

Sample Input 1

1
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1

Sample Output 1

6