Футбольная команда построилась в несколько рядов, чтобы сфотографироваться. Расположение каждого игрока дано в виде пары целых x и y, где y задает номер ряда, а x — расстояние от игрока до левого края строки. Все координаты x различны.
Для того, чтобы сделать фото более красивым, вы хотите, чтобы игроки, которые находятся рядом друг с другом, одели футболки разных цветов. Точнее, для каждого игрока 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