Задача из Черёмушек
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хошино Аква — гениальный ребёнок-актёр из знаменитого посёлка Черёмушки. Недавно он вместе со своей сестрой Руби переехал в Токио, чтобы помочь ей стать великим айдолом.

Руби уже состоит в айдол группе «B-Komachi», вместе с Каной и Мем-чо. Группа готовится к серии из $$$t$$$ выступлений. Каждое выступление будет проведено на сцене, представляющей из себя нестрого выпуклый многоугольник с $$$n$$$ вершинами, то есть такой, в котором некоторые вершины могут лежать на сторонах, а не только в углах.

Аква быстро заметил, что вершины сцены — это крепления для кабелей студийной аппаратуры. Он решил провести два кабеля через всю сцену, соединяя вершины, чтобы разбить её на три отдельные секции — по одной для каждой участницы. Однако просто разбить недостаточно для успеха, Аква хочет, чтобы площади трёх секций относились как $$$a$$$ : $$$b$$$ : $$$c$$$.

Поскольку Аква — актёр, а не программист, вам, как менеджеру «B-Komachi», предстоит посчитать количество способов провести два кабеля, чтобы сцена разделилась на три секции с заданным отношением площадей. Только так группа сможет достичь звёздного успеха на каждом выступлении!

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

В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество выступлений.

Для каждого выступления:

Гарантируется, что сумма $$$n$$$ по всем выступлениям не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого выступления выведите одно целое число — количество способов провести два кабеля, чтобы сцена разделилась на три секции с отношением площадей $$$a$$$ : $$$b$$$ : $$$c$$$.

Примеры

Входные данные
2
8
0 0
1 0
2 0
2 1
2 2
1 2
0 2
0 1
1 3 4
5
0 0
2 0
2 2
1 3
0 2
2 4 4
Выходные данные
12
4
Входные данные
1
8
0 0
0 5
9 5
10 5
12 5
12 0
10 0
9 0
45 5 10
Выходные данные
3

Примечание

Все варианты расположения кабелей для двух выступлений в первом примере из условия.