题目描述

酒店收到了 $N$ 张订单，每张订单需要安排若干个房间，并且客人会连续入住若干天。具体地，第 $i$ 张订单包含三个整数 $A_i, B_i, C_i$，表示需要 $A_i$ 个房间，从第 $B_i$ 天开始入住，连续住 $C_i$ 天（即入住时间为第 $B_i$ 天到第 $B_i + C_i - 1$ 天）。同一张订单的客人在入住期间不会更换房间。

现在需要合理安排房间，使得能够同时满足所有订单的要求，求最少需要多少个房间。

输入格式

第一行一个整数 $T$，表示测试数据的组数。

每组测试数据的第一行包含一个整数 $N$，表示订单的数量。

接下来 $N$ 行，每行三个整数 $A_i, B_i, C_i$，分别表示需要的房间数、开始入住的天数以及连续入住的天数。

输出格式

对于每组测试数据，输出一行一个整数，表示满足所有订单所需的最少房间数。

样例

1
3
3 10 4
4 9 3
7 8 9

14

数据范围与提示

• $1 \le T \le 100$
• $1 \le N \le 10000$
• $1 \le A_i \le 10$
• $1 \le B_i \le 180$
• $1 \le C_i \le 10$