{"raw_statement":[{"iden":"statement","content":"В галерее наночастиц Галактической федерации проводится выставка электронов. Каждому купившему входной билет разрешается понаблюдать за полётом одного электрона и сделать один снимок на свой нанофотоаппарат.\n\nПолёт электрона начинается в точке (0, 0), далее он перемещается по прямой в точку (1, 1), затем в точку (3,  - 1), затем в точку (6, 2), затем в точку (10,  - 2) и т. д. Таким образом, на i-м шаге X-координата электрона увеличивается на i, а Y-координата увеличивается на i, если шаг нечётный, и уменьшается на i, если шаг чётный. Электрон летит по описанной траектории бесконечно.\n\nИз-за того, что электрон движется очень быстро, на снимок попадает не вся траектория, а только точки, в которых электрон меняет своё направление. Вам необходимо посчитать количество таких точек, находящихся строго внутри прямоугольника с координатами левой нижней точки (Lx, Ly) и правой верхней точки (Rx, Ry). Точка начала движения электрона не считается точкой смены направления.\n\nВ первой строке задано количество тестов T (1 ≤ T ≤ 10000).\n\nВ следующих T строках заданы тесты в виде координат прямоугольника Lx, Ly, Rx, Ry ( - 1018 ≤ Lx < Rx ≤ 1018,  - 1018 ≤ Ly < Ry ≤ 1018).\n\nДля каждого теста выведите количество точек смены направления электрона внутри прямоугольника.\n\n"},{"iden":"входные данные","content":"В первой строке задано количество тестов T (1 ≤ T ≤ 10000).В следующих T строках заданы тесты в виде координат прямоугольника Lx, Ly, Rx, Ry ( - 1018 ≤ Lx < Rx ≤ 1018,  - 1018 ≤ Ly < Ry ≤ 1018)."},{"iden":"выходные данные","content":"Для каждого теста выведите количество точек смены направления электрона внутри прямоугольника."},{"iden":"пример","content":"Входные данные50 -3 8 40 0 7 31 1 6 2-1 -2 5 01 -3 11 0Выходные данные32012"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor 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.  \n\nThe electron’s trajectory consists of points $ P_i = (x_i, y_i) $ for $ i \\geq 1 $, where:  \n- $ x_i = \\sum_{j=1}^{i} j = \\frac{i(i+1)}{2} $,  \n- $ y_i = \\sum_{j=1}^{i} (-1)^{j+1} j $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10000 $  \n2. For each test case:  \n   $ -10^{18} \\leq L_x < R_x \\leq 10^{18} $,  \n   $ -10^{18} \\leq L_y < R_y \\leq 10^{18} $  \n\n**Objective**  \nFor each test case, count the number of points $ P_i = (x_i, y_i) $, $ i \\geq 1 $, such that:  \n$$\nL_x < x_i < R_x \\quad \\text{and} \\quad L_y < y_i < R_y\n$$  \nwhere  \n$$\nx_i = \\frac{i(i+1)}{2}, \\quad y_i = \\sum_{j=1}^{i} (-1)^{j+1} j\n$$  \n\nNote: $ y_i = \\begin{cases} \n\\frac{i+1}{2} & \\text{if } i \\text{ is odd} \\\\\n-\\frac{i}{2} & \\text{if } i \\text{ is even}\n\\end{cases} $","simple_statement":"An electron starts at (0,0) and moves in steps. On step i:\n\n- Its x-coordinate increases by i.\n- Its y-coordinate increases by i if i is odd, decreases by i if i is even.\n\nIt changes direction after each step. We care only about the points where it changes direction (not the start).\n\nGiven a rectangle with bottom-left (Lx, Ly) and top-right (Rx, Ry), count how many of these direction-change points lie strictly inside the rectangle.\n\nInput: T test cases. For each, given Lx, Ly, Rx, Ry.\n\nOutput: For each test, print the count of such points inside the rectangle.","has_page_source":false}