В галерее наночастиц Галактической федерации проводится выставка электронов. Каждому купившему входной билет разрешается понаблюдать за полётом одного электрона и сделать один снимок на свой нанофотоаппарат.
Полёт электрона начинается в точке (0, 0), далее он перемещается по прямой в точку (1, 1), затем в точку (3, - 1), затем в точку (6, 2), затем в точку (10, - 2) и т. д. Таким образом, на i-м шаге X-координата электрона увеличивается на i, а Y-координата увеличивается на i, если шаг нечётный, и уменьшается на i, если шаг чётный. Электрон летит по описанной траектории бесконечно.
Из-за того, что электрон движется очень быстро, на снимок попадает не вся траектория, а только точки, в которых электрон меняет своё направление. Вам необходимо посчитать количество таких точек, находящихся строго внутри прямоугольника с координатами левой нижней точки (Lx, Ly) и правой верхней точки (Rx, Ry). Точка начала движения электрона не считается точкой смены направления.
В первой строке задано количество тестов T (1 ≤ T ≤ 10000).
В следующих T строках заданы тесты в виде координат прямоугольника Lx, Ly, Rx, Ry ( - 1018 ≤ Lx < Rx ≤ 1018, - 1018 ≤ Ly < Ry ≤ 1018).
Для каждого теста выведите количество точек смены направления электрона внутри прямоугольника.
## Входные Данные
В первой строке задано количество тестов T (1 ≤ T ≤ 10000).В следующих T строках заданы тесты в виде координат прямоугольника Lx, Ly, Rx, Ry ( - 1018 ≤ Lx < Rx ≤ 1018, - 1018 ≤ Ly < Ry ≤ 1018).
## Выходные Данные
Для каждого теста выведите количество точек смены направления электрона внутри прямоугольника.
## Пример
Входные данные50 -3 8 40 0 7 31 1 6 2-1 -2 5 01 -3 11 0Выходные данные32012
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $, define a rectangle $ R_k = [L_x, R_x] \times [L_y, R_y] $ with integer coordinates.
The electron’s trajectory consists of points $ P_i = (x_i, y_i) $ for $ i \geq 1 $, where:
- $ x_i = \sum_{j=1}^{i} j = \frac{i(i+1)}{2} $,
- $ y_i = \sum_{j=1}^{i} (-1)^{j+1} j $.
**Constraints**
1. $ 1 \leq T \leq 10000 $
2. For each test case:
$ -10^{18} \leq L_x < R_x \leq 10^{18} $,
$ -10^{18} \leq L_y < R_y \leq 10^{18} $
**Objective**
For each test case, count the number of points $ P_i = (x_i, y_i) $, $ i \geq 1 $, such that:
$$
L_x < x_i < R_x \quad \text{and} \quad L_y < y_i < R_y
$$
where
$$
x_i = \frac{i(i+1)}{2}, \quad y_i = \sum_{j=1}^{i} (-1)^{j+1} j
$$
Note: $ y_i = \begin{cases}
\frac{i+1}{2} & \text{if } i \text{ is odd} \\
-\frac{i}{2} & \text{if } i \text{ is even}
\end{cases} $