Little John is as little as night is day — he was known to be a giant, at possibly $2.1$ metres tall. It has everything to do with his love for milk.

His dairy diary has $n$ entries, showing that he acquired $a_i$ pints of fresh milk on day $d_i$. Milk declines in freshness with time and stays drinkable for a maximum of $k$ days. In other words, fresh milk acquired on day $d_i$ will be drinkable between days $d_i$ and $d_i+k-1$ inclusive.

Every day, Little John drinks drinkable milk, up to a maximum of $m$ pints. In other words, if there are less than $m$ pints of milk, he will drink them all and not be satisfied; if there are at least $m$ pints of milk, he will drink exactly $m$ pints and be satisfied, and it's a milk satisfaction day.

Little John always drinks the freshest drinkable milk first.

Determine the number of milk satisfaction days for Little John.

Input

The first line of the input contains a single integer $t$ ($1\leq t \leq 10^4$), the number of test cases.

The first line of each test case consists of three integers $n$, $m$, $k$ ($1\le n$, $m$, $k \le 10^5$), the number of diary entries, the maximum pints needed for a milk satisfaction day, and the duration of milk's freshness.

Then follow $n$ lines of each test case, each with two integers $d_i$ and $a_i$ ($1\le d_i$, $a_i \le 10^6$), the day on which the milk was acquired and the number of pints acquired. They are sorted in increasing values of $d_i$, and all values of $d_i$ are distinct.

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

Output

For each test case, output a single integer, the number of milk satisfaction days.

见题面 Input 部分

见题面 Output 部分

In the first test case, $5$ pints of milk are good for $3$ days before spoiling.

In the second test case, the following will happen:

• On day $1$, he will receive $5$ pints of milk and drink $3$ of them (leaving $2$ pints from day $1$);
• On day $2$, he will receive $7$ pints of milk and drink $3$ of them (leaving $2$ pints from day $1$ and $4$ pints from day $2$);
• On day $3$, he will drink $3$ pints from day $2$ (leaving $2$ pints from day $1$ and $1$ pint from day $2$);
• On day $4$, the milk acquired on day $1$ will spoil, and he will drink $1$ pint from day $2$ (no more milk is left).