Точками решетки называются точки на координатной плоскости с целочисленными координатами. Внутренней точкой решетки будем называть точку решетки, лежащую внутри заданного многоугольника, но не на его границе. Например, ниже приведен треугольник с шестью внутренними точками решетки.

Напишите программу, которая считывает три пары координат (xA, yA), (xB, yB), (xC, yC), каждая из которых является беззнаковым целым числом, не большим 100. Числа в строке разделяются одним пробелом и задаются в порядке xA yA xB yB xC yC. Эти координаты описывают три разные (но возможно коллинеарные) точки решетки. Если точки задают треугольник с ненулевой площадью, то следует вывести количество внутренних точек решетки в треугольнике. Иначе следует вывести ноль (если точки коллинеарны, то внутренние точки решетки отсутствуют).

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

Начинаются целым числом n (0 ≤ n ≤ 255). Далее следует n тестов. Каждый тест задается списком из шести беззнаковых целых чисел, не превосходящих 100. Шесть целых чисел xA yA xB yB xC yC соответствуют координатам (xA, yA), (xB, yB), (xC, yC).

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

Для каждого теста вывести в отдельной строке количество внутренних точек решетки.