Профессор Пан играет в китайские шашки. Игровое поле такое же, как на рисунке выше. На доске находится $n$ шашек. Профессор Пан хочет узнать, сколько различных ходов можно сделать на текущей доске.

Один ход состоит из нескольких шагов. Сначала профессор Пан должен выбрать одну шашку $a$ для перемещения. На каждом шаге профессор Пан должен выбрать другую шашку $b$ в качестве опорной и переместить шашку $a$ в симметричную относительно шашки $b$ позицию. (В рамках одного хода профессор Пан не может менять выбор шашки $a$ между шагами. Если после шага шашка $a$ возвращается в позицию, в которой она находилась до начала хода, такой шаг запрещен.) Существует несколько условий относительно опорной шашки $b$:

• Отрезок, соединяющий $a$ и $b$, должен быть параллелен одной из координатных осей. Примечание: на гексагональной доске есть три оси. Одна из них горизонтальная, и любые две оси пересекаются под углом $\pi/3$.
• $a$ и $b$ не обязательно должны быть соседними.
• На отрезке, соединяющем $a$ и его симметричную позицию, не должно быть других шашек, кроме $b$.
• Симметричная позиция должна находиться на гексагональной доске и не должна быть занята никакой другой шашкой.

Ход должен состоять как минимум из одного шага. После первого шага профессор Пан может остановиться в любой момент. Профессор Пан может выбрать любую шашку на доске в качестве перемещаемой. Выведите количество различных ходов, которые может сделать профессор Пан. Два хода считаются различными тогда и только тогда, когда наборы позиций всех шашек после этих двух ходов различаются, то есть шашки неразличимы.

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

Первая строка содержит целое число $T$ ($1 \le T \le 100$) — количество тестовых случаев. Для каждого тестового случая первая строка содержит целое число $n$ ($1 \le n \le 121$) — количество шашек. Каждая из следующих $n$ строк содержит два целых числа, указывающих позицию шашки. Первое число указывает номер строки, а второе число указывает порядковый номер шашки в этой строке. Нумерация ведется сверху вниз и слева направо, начиная с 1. Гарантируется, что позиции шашек различны.

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

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

Примеры

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

5
1
1 1
2
1 1
2 1
2
9 4
9 6
10
1 1
2 1
2 2
3 1
3 2
3 3
4 1
4 2
4 3
4 4
10
1 1
2 1
2 2
5 7
3 2
3 3
4 1
4 2
4 3
4 4

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

0
1
2
6
13