AT_abc458_g [ABC458G] Children Yearn for the Evil Kindergarten

$ 10^{100} $ 人の園児がゲーム会場にいます。はじめはどの園児もメダルを持っていません。 園児は、**脱落**か**脱出**のいずれかをした時点で、またその時点に限り、会場を去ります。 ゲームは $ N $ 日からなります。 $ i $ 日目 ( $ 1 \leq i \leq N $ ) は以下の一連の処理を順に実行します。 - 会場にいる園児の持っているメダルをすべて回収し、その合計枚数を $ s $ とおく。 - $ s + A_i $ 枚のメダルを、会場にいる園児のあいだで自由に分配する(会場に園児がいない場合は何もしない)。 - 会場にいる園児のうち、メダル所持数が $ B_i $ 枚未満の者は脱落する。メダル所持数が $ B_i $ 枚以上の者は、メダルを $ B_i $ 枚ずつ失う。 - 会場にいる園児のうち、メダル所持数が $ C_i $ 枚以上の者は、各々がこのタイミングで脱出するか会場に残るかを選ぶ。 $ N $ 日間が終わった時点で会場に残っている園児は、脱落します。 最終的に脱出する園児の人数としてあり得る最大値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

各テストケースに対する答えを順に、改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。園児たちが以下のように行動することで、脱出人数は $ 5 $ 人になります。 - $ 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 $ 枚持っている園児 $ 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 $ 番目のテストケースにおいて、園児は $ 1 $ 人も脱出できません。 ### 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 $ - 全てのテストケースにおける $ N $ の総和は $ 3 \times 10^5 $ 以下 - 入力される値はすべて整数