AT_abc458_g.Children Yearn for the Evil Kindergarten

There are $10^{100}$ kids at a game venue. Initially, no kid has any medals.

A kid leaves the venue exactly when they either drop out or escape.

The game consists of $N$ days. On day $i$ ($1 \leq i \leq N$), the following sequence of operations is performed in order.

• Collect all medals held by the kids at the venue, and let $s$ be the total number of collected medals.
• Distribute $s + A_i$ medals freely among the kids at the venue (if there are no kids at the venue, do nothing).
• Among the kids at the venue, those with fewer than $B_i$ medals drop out. Those with at least $B_i$ medals each lose $B_i$ medals.
• Among the kids at the venue, those with at least $C_i$ medals each choose whether to escape at this point or remain at the venue.

Kids who remain at the venue at the end of the $N$ days drop out.

Find the maximum possible number of kids who ultimately escape.

You are given $T$ test cases; solve each of them.

游戏场地中有 $10^{100}$ 个孩子。初始时，没有任何孩子拥有奖牌。

一个孩子恰好在以下两种情形之一发生时离开场地：退出或逃离。

游戏共持续 $N$ 天。在第 $i$ 天（$1 \leq i \leq N$），按顺序执行如下操作：

• 收集所有仍在场地内的孩子所持有的奖牌，记收集到的奖牌总数为 $s$；
• 将 $s + A_i$ 枚奖牌自由地分发给仍在场地内的孩子（若此时场内没有孩子，则不进行任何操作）；
• 在仍在场地内的孩子中，持有少于 $B_i$ 枚奖牌者退出；持有至少 $B_i$ 枚奖牌者每人失去 $B_i$ 枚奖牌；
• 在仍在场地内的孩子中，持有至少 $C_i$ 枚奖牌者每人可选择此时逃离场地，或继续留在场地内。

在 $N$ 天结束时仍留在场地内的孩子将退出。

求最终能够逃离场地的孩子数量的最大可能值。

你将得到 $T$ 组测试数据，请对每组数据分别求解。

The input is given from Standard Input in the following format:

$T$
$\mathrm{case}_{1}$
$\mathrm{case}_{2}$
$\vdots$
$\mathrm{case}_{T}$

Each test case is given in the following format:

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_N$ $B_N$ $C_N$

输入从标准输入中按以下格式给出：

$T$
$\mathrm{case}_{1}$
$\mathrm{case}_{2}$
$\vdots$
$\mathrm{case}_{T}$

每个测试用例按以下格式给出：

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_N$ $B_N$ $C_N$

Output the answers for the test cases in order, separated by newlines.

按顺序输出测试用例的答案，答案之间用换行符分隔。

Sample 1 Explanation:
Consider the first test case. By acting as follows, five kids can escape.

• At the start of day $1$, collect $s = 0$ medals from $10^{100}$ kids. Then, proceed as follows.
  • Distribute $0 + 16 = 16$ medals so that the kids' medal counts become $(5, 5, 2, 2, 2, 0, \dots, 0)$.
  • The $10^{100} - 5$ kids with no medals drop out, and the remaining $5$ kids' medal counts become $(3, 3, 0, 0, 0)$.
  • The $2$ kids with $3$ medals each choose to escape, and the remaining $3$ kids' medal counts become $(0, 0, 0)$.
• At the start of day $2$, collect $s = 0$ medals from $3$ kids. Then, proceed as follows.
  • Distribute $0 + 15 = 15$ medals so that the kids' medal counts becomes $(6, 6, 3)$.
  • No one drops out, and the remaining $3$ kids' medal counts become $(4, 4, 1)$.
  • $1$ kid with $4$ medals chooses to escape, and the remaining $2$ kids' medal counts become $(4, 1)$.
• At the start of day $3$, collect $s = 5$ medals from $2$ kids. Then, proceed as follows.
  • Distribute $5 + 1 = 6$ medals so that the kids' medal counts becomes $(3, 3)$.
  • No one drops out, and the remaining $2$ kids' medal counts become $(0, 0)$.
  • No one escapes.
• At the start of day $4$, collect $s = 0$ medals from $2$ kids. Then, proceed as follows.
  • Distribute $0 + 20 = 20$ medals so that the kids' medal counts becomes $(10, 10)$.
  • No one drops out, and the remaining $2$ kids' medal counts become $(5, 5)$.
  • The $2$ kids with $5$ medals each choose to escape, and the venue becomes empty.

In the second test case, not a single kid can escape.

Constraints

• $1 \leq T \leq 3 \times 10^5$
• $1 \leq N \leq 3 \times 10^5$
• $1 \leq A_i \leq 10^6$
• $1 \leq B_i \leq 10^6$
• $1 \leq C_i \leq 10^6$
• The sum of $N$ over all test cases is at most $3 \times 10^5$.
• All input values are integers.

样例 1 解释：
考虑第一个测试用例。通过如下操作，可使五名儿童成功逃脱。

• 第 1 天开始时，从 $10^{100}$ 名儿童处收集 $s = 0$ 枚奖牌。随后执行以下步骤：
  • 分发 $0 + 16 = 16$ 枚奖牌，使得儿童的奖牌数变为 $(5, 5, 2, 2, 2, 0, \dots, 0)$。
  • 没有获得奖牌的 $10^{100} - 5$ 名儿童退出，剩余 $5$ 名儿童的奖牌数变为 $(3, 3, 0, 0, 0)$。
  • 两名拥有 $3$ 枚奖牌的儿童选择逃脱，剩余 $3$ 名儿童的奖牌数变为 $(0, 0, 0)$。
• 第 2 天开始时，从 $3$ 名儿童处收集 $s = 0$ 枚奖牌。随后执行以下步骤：
  • 分发 $0 + 15 = 15$ 枚奖牌，使得儿童的奖牌数变为 $(6, 6, 3)$。
  • 无人退出，剩余 $3$ 名儿童的奖牌数变为 $(4, 4, 1)$。
  • 一名拥有 $4$ 枚奖牌的儿童选择逃脱，剩余 $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$ 枚奖牌的儿童选择逃脱，场地清空。

在第二个测试用例中，没有任何一名儿童能够逃脱。

约束条件

• $1 \leq T \leq 3 \times 10^5$
• $1 \leq N \leq 3 \times 10^5$
• $1 \leq A_i \leq 10^6$
• $1 \leq B_i \leq 10^6$
• $1 \leq C_i \leq 10^6$
• 所有测试用例的 $N$ 之和不超过 $3 \times 10^5$。
• 所有输入值均为整数。