Хошино Аква — гениальный ребёнок-актёр из знаменитого посёлка Черёмушки. Недавно он вместе со своей сестрой Руби переехал в Токио, чтобы помочь ей стать великим айдолом.
Руби уже состоит в айдол группе «B-Komachi», вместе с Каной и Мем-чо. Группа готовится к серии из $$$t$$$ выступлений. Каждое выступление будет проведено на сцене, представляющей из себя нестрого выпуклый многоугольник с $$$n$$$ вершинами, то есть такой, в котором некоторые вершины могут лежать на сторонах, а не только в углах.
Аква быстро заметил, что вершины сцены — это крепления для кабелей студийной аппаратуры. Он решил провести два кабеля через всю сцену, соединяя вершины, чтобы разбить её на три отдельные секции — по одной для каждой участницы. Однако просто разбить недостаточно для успеха, Аква хочет, чтобы площади трёх секций относились как $$$a$$$ : $$$b$$$ : $$$c$$$.
Поскольку Аква — актёр, а не программист, вам, как менеджеру «B-Komachi», предстоит посчитать количество способов провести два кабеля, чтобы сцена разделилась на три секции с заданным отношением площадей. Только так группа сможет достичь звёздного успеха на каждом выступлении!
В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество выступлений.
Для каждого выступления:
Гарантируется, что любая пара различных вершин не совпадает.
Гарантируется, что сумма $$$n$$$ по всем выступлениям не превосходит $$$2 \cdot 10^5$$$.
Для каждого выступления выведите одно целое число — количество способов провести два кабеля, чтобы сцена разделилась на три секции с отношением площадей $$$a$$$ : $$$b$$$ : $$$c$$$.
280 01 02 02 12 21 20 20 11 3 450 02 02 21 30 22 4 4
12 4
180 00 59 510 512 512 010 09 045 5 10
3
Все варианты расположения кабелей для двух выступлений в первом примере из условия.