Фотография футболистов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Футбольная команда построилась в несколько рядов, чтобы сфотографироваться. Расположение каждого игрока дано в виде пары целых x и y, где y задает номер ряда, а x — расстояние от игрока до левого края строки. Все координаты x различны.

Для того, чтобы сделать фото более красивым, вы хотите, чтобы игроки, которые находятся рядом друг с другом, одели футболки разных цветов. Точнее, для каждого игрока P:

- ближайший игрок справа от P в том же ряду (если такой игрок есть) должен носить футболку другого цвета,
- ближайший игрок справа от P в предыдущей строке (если такой игрок есть) должен носить футболку другого цвета,
- ближайший игрок справа от P в следующей строке (если такой игрок есть) должен носить футболку другого цвета.

Более формально, если есть игроки с координатами (x1,y1) и (x2,y2), где x1<x2, то эти два игрока должны носить футболки разных цветов, если: y1- 1 ≤y2≤y1+ 1 и нет игрока с координатами (x3,y2) для всех x1<x3<x2.

Найдите минимальное число цветов футболок, необходимых для того, чтобы это было возможно.

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

Первая строка входного файла содержит одно целое число t, количество тестов. Каждый тест начинается со строки, содержащей целое число n — количество игроков, а затем n строк, содержащих пары xi yi.

Ограничения: 1 ≤T≤ 100, 1 ≤x≤ 1000, все значения xi различны.

В задаче 1: 1 ≤y≤ 15, 1 ≤N≤ 100.

В задаче 2: 1 ≤y≤ 30, 1 ≤N≤ 1000.

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

Выведите для каждого теста одно число — минимальное число цветов

Примеры тестов

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

    3
    3
    10 10
    8 15
    12 7
    5
    1 1
    2 1
    3 1
    4 1
    5 1
    3
    1 1
    2 2
    3 1

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

    1
    2
    3