{"problem":{"name":"E. Галерея","description":{"content":"В галерее наночастиц Галактической федерации проводится выставка электронов. Каждому купившему входной билет разрешается понаблюдать за полётом одного электрона и сделать один снимок на свой нанофотоа","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10136E"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nВ первой строке задано количество тестов T (1 ≤ T ≤ 10000).В следующих T строках заданы тесты в виде координат прямоугольника Lx, Ly, Rx, Ry ( - 1018 ≤ Lx < Rx ≤ 1018,  - 1018 ≤ Ly < Ry ≤ 1018).\n\n## Выходные Данные\n\nДля каждого теста выведите количество точек смены направления электрона внутри прямоугольника.\n\n## Пример\n\nВходные данные50 -3 8 40 0 7 31 1 6 2-1 -2 5 01 -3 11 0Выходные данные32012\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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} $","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10136E","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}