C. Занятой робот
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть робот, который двигается по числовой прямой. В момент времени $$$0$$$ он находится в точке $$$0$$$.

Вы посылаете роботу $$$n$$$ команд: в $$$t_i$$$-ю секунды вы указываете робот пойти в точку $$$x_i$$$. Когда робот получает команду, он сразу же начинает движение в сторону точки $$$x_i$$$ со скоростью $$$1$$$ в секунду и останавливается, когда достигает этой точки. Однако, когда робот двигается, он игнорирует все другие команды, которые он получает.

Например, предположим, что роботу приходят три команды: в секунду $$$1$$$ ехать в точку $$$5$$$, в секунду $$$3$$$ ехать в точку $$$0$$$ и в секунду $$$6$$$ ехать в точку $$$4$$$. Тогда робот будет стоять в $$$0$$$ до секунды $$$1$$$, затем начнет ехать к $$$5$$$, игнорируя вторую команду, достигнет $$$5$$$ в момент времени $$$6$$$ и сразу же начнет ехать к $$$4$$$, чтобы выполнить третью команду. В момент времени $$$7$$$ он доедет до $$$4$$$ и остановится там.

Команда $$$i$$$ считается выполненной успешно, если существует такой момент времени в отрезке $$$[t_i, t_{i + 1}]$$$ (то есть после того, как команда послана, и перед тем, как послана следующая, обе границы включительно; считаем $$$t_{n + 1} = +\infty$$$), что робот находится в позиции $$$x_i$$$. Посчитайте количество успешных команд. Обратите внимание, что проигнорированная команда все равно может быть успешной.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Затем следует описание наборов входных данных.

В первой строке набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество команд.

Затем $$$n$$$ строк описывают команды. В $$$i$$$-й из них записаны два целых числа $$$t_i$$$ и $$$x_i$$$ ($$$1 \le t_i \le 10^9$$$, $$$-10^9 \le x_i \le 10^9$$$) — время и точка назначения $$$i$$$-й команды.

Команды упорядочены по времени, то есть, $$$t_i < t_{i + 1}$$$ для всех возможных $$$i$$$.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество успешных команд.

Пример
Входные данные
8
3
1 5
3 0
6 4
3
1 5
2 4
10 -5
5
2 -5
3 1
4 1
5 1
6 1
4
3 3
5 -3
9 2
12 0
8
1 1
2 -6
7 2
8 3
12 -9
14 2
18 -1
23 9
5
1 -4
4 -7
6 -1
7 -3
8 -7
2
1 2
2 -2
6
3 10
5 5
8 0
12 -4
14 -7
19 -5
Выходные данные
1
2
0
2
1
1
0
2
Примечание

Движение робота в первом наборе входных данных описано в условии задачи. Только последняя команда успешна.

Во втором наборе входных данных вторая команда успешна: робот проходит через точку назначения $$$4$$$ в момент времени $$$5$$$. К тому же, последняя команда тоже в конце концов станет успешной.

В третьем наборе входных данных ни одна команда не успешна, и робот остановится в $$$-5$$$ в секунду $$$7$$$.

Вот $$$0$$$-индексированные последовательности позиций робота в каждую секунду для каждого набора входных данных из примера. Все отрезанные позиции совпадают с последней:

  1. $$$[0, 0, 1, 2, 3, 4, 5, 4, 4, \dots]$$$
  2. $$$[0, 0, 1, 2, 3, 4, 5, 5, 5, 5, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -5, \dots]$$$
  3. $$$[0, 0, 0, -1, -2, -3, -4, -5, -5, \dots]$$$
  4. $$$[0, 0, 0, 0, 1, 2, 3, 3, 3, 3, 2, 2, 2, 1, 0, 0, \dots]$$$
  5. $$$[0, 0, 1, 0, -1, -2, -3, -4, -5, -6, -6, -6, -6, -7, -8, -9, -9, -9, -9, -8, -7, -6, -5, -4, -3, -2, -1, -1, \dots]$$$
  6. $$$[0, 0, -1, -2, -3, -4, -4, -3, -2, -1, -1, \dots]$$$
  7. $$$[0, 0, 1, 2, 2, \dots]$$$
  8. $$$[0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5, -6, -7, -7, \dots]$$$