题目描述

游戏会场内有 $10^{100}$ 名园儿。最初,所有园儿都没有任何奖牌。

园儿仅在脱落或脱出时离开会场。

游戏共持续 $N$ 天。第 $i$ 天 ($1 \le i \le N$) 按顺序执行以下操作:

1. 收回会场内所有园儿持有的奖牌,设总数为 $s$。
2. 将 $s + A_i$ 枚奖牌自由分配给会场内的园儿(若会场无人则不操作)。
3. 持有奖牌数少于 $B_i$ 的园儿脱落;持有奖牌数 $\ge B_i$ 的园儿各失去 $B_i$ 枚奖牌。
4. 持有奖牌数 $\ge C_i$ 的园儿,可各自选择脱出或留在会场。

$N$ 天结束后仍留在会场的园儿全部脱落。

求最终能脱出的园儿人数的最大值。给定 $T$ 个测试用例,分别求解。

输入格式

T
case_1
case_2
⋮
case_T

每个测试用例的格式:

N
A_1 B_1 C_1
A_2 B_2 C_2
⋮
A_N B_N C_N

输出格式

按顺序输出每个测试用例的答案,以换行分隔。

数据范围

• $1 \le T \le 3 \times 10^5$
• $1 \le N \le 3 \times 10^5$
• $1 \le A_i, B_i, C_i \le 10^6$
• 所有测试用例的 $N$ 之和 $\le 3 \times 10^5$
• 所有输入均为整数

样例 1 输入

2
4
16 2 3
15 2 4
1 3 5
20 5 5
2
41404 1 941738
211877 205711 417821

样例 1 输出

5
0

第 1 个测试用例的说明

通过如下行动可使 $5$ 名园儿脱出:

• 第 1 天:从 $10^{100}$ 名园儿处收回 $s = 0$ 枚奖牌。

  • 分配 $0 + 16 = 16$ 枚奖牌,使各园儿的奖牌数为 $(5, 5, 2, 2, 2, 0, \ldots, 0)$。
  • 持有 $0$ 枚的 $10^{100} - 5$ 名园儿脱落,剩余 $5$ 人奖牌数变为 $(3, 3, 0, 0, 0)$。
  • 持有 $3$ 枚的 $2$ 名园儿选择脱出,剩余 $3$ 人奖牌数为 $(0, 0, 0)$。

• 第 2 天:从 $3$ 名园儿处收回 $s = 0$ 枚奖牌。

  • 分配 $0 + 15 = 15$ 枚奖牌,使各园儿奖牌数为 $(6, 6, 3)$。
  • 无人脱落,剩余 $3$ 人奖牌数变为 $(4, 4, 1)$。
  • 持有 $4$ 枚的 $1$ 名园儿选择脱出,剩余 $2$ 人奖牌数为 $(4, 1)$。

• 第 3 天:从 $2$ 名园儿处收回 $s = 5$ 枚奖牌。

  • 分配 $5 + 1 = 6$ 枚奖牌,使各园儿奖牌数为 $(3, 3)$。
  • 无人脱落,剩余 $2$ 人奖牌数变为 $(0, 0)$。
  • 无人脱出。

• 第 4 天:从 $2$ 名园儿处收回 $s = 0$ 枚奖牌。

  • 分配 $0 + 20 = 20$ 枚奖牌,使各园儿奖牌数为 $(10, 10)$。
  • 无人脱落,剩余 $2$ 人奖牌数变为 $(5, 5)$。
  • 持有 $5$ 枚的 $2$ 名园儿选择脱出,会场清空。

第 2 个测试用例的说明

第 2 个测试用例中,无任何园儿可以脱出。