K. Signals That Don't Wait
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

An isolated observatory has an antenna powered by a battery. During the next $$$n$$$ days the observatory will generate one message per day. Each message can only be transmitted on the day it is generated; if it is not transmitted, it is lost forever.

The battery is initially empty and its available capacity may change from one day to another.

For each day $$$i$$$ three integers are known:

  • $$$r_i$$$: the amount of energy the generator delivers that day.
  • $$$c_i$$$: the maximum capacity of the battery that day.
  • $$$a_i$$$: the energy needed to transmit that day's message.

If the battery contains $$$E$$$ units of energy at the end of the previous day, day $$$i$$$ happens in this order:

  1. The capacity is adjusted and the recharge takes place: the available energy becomes $$$E = \min(c_i, E + r_i)$$$. All energy exceeding the capacity is lost for good.
  2. The day's message can be transmitted if $$$E \geq a_i$$$. In that case exactly $$$a_i$$$ units of energy are consumed. It is also possible to choose not to transmit it, even if there is enough energy.
  3. The remaining energy is kept for the next day.

It is not possible to transmit before the recharge, to save a message for another day, or to transmit it partially. There are no other energy consumptions.

The data for all days is known from the beginning.

Determine the maximum number of messages that can be transmitted during the $$$n$$$ days.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^{4}$$$), the number of test cases.

For each test case:

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \times 10^{5}$$$).

Each of the following $$$n$$$ lines contains three integers $$$r_i, c_i, a_i$$$ ($$$0 \leq r_i \leq 10^{9}$$$, $$$1 \leq c_i \leq 10^{9}$$$, $$$1 \leq a_i \leq 10^{9}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^{5}$$$.

The capacity $$$c_i$$$ may increase or decrease from one day to another. It is not guaranteed that $$$a_i \leq c_i$$$.

Output

For each test case, print an integer: the maximum number of messages that can be transmitted.

Example
Input
4
3
10 10 10
3 10 9
0 10 2
3
6 6 6
0 6 3
0 6 3
5
8 8 5
0 2 2
4 6 3
1 6 2
0 6 1
2
0 5 1
2 1 2
Output
2
2
4
0
Note

Explanation for example 1

In the first case, the messages of days $$$1$$$ and $$$3$$$ can be transmitted. After the first transmission the battery is empty; on the second day it receives $$$3$$$ units, which are kept for the third day. The three messages cannot all be transmitted because, after sending the first one, there is not enough energy left for the second.

In the second case it is better not to transmit the first message: this way the initial $$$6$$$ units allow transmitting the messages of days $$$2$$$ and $$$3$$$.

In the third case the messages of days $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$ can be transmitted. The energy at the end of each of those days is, respectively, $$$3$$$, $$$0$$$, $$$1$$$ and $$$0$$$. In particular, at the start of the second day the capacity reduction makes the available energy drop from $$$3$$$ to $$$2$$$. The fifth message cannot be added to this plan: transmitting all five messages is impossible.

In the fourth case, there is no energy on the first day. On the second day, although the generator delivers $$$2$$$ units, the battery can only store $$$1$$$, so the message cannot be transmitted either.