{"raw_statement":[{"iden":"statement","content":"On Planet E, there are many stars!\n\nTo be precise, the sky is a 2-d plane and there are infinitely many stars, one at each integral point ($(x, y)$ where both $x$ and $y$ are integers).\n\nPeople on Planet E have a hobby of drawing straight segments between the stars. One day, they are curious about how many stars their straight segments have covered.\n\nCan you help the people on Planet E to count the number of stars on their straight segments?\n\nThe first line contains a positive integer $T$ ($T <= 100$), the number of testcases.\n\nEach testcase contains 4 integers $x_0, y_0, x_1, y_1$ ($| x_i | <= 10^9$ and $| y_i | <= 10^9$ for $i = 0, 1$), representing the segment $(x_0, y_0)$ to $(x_1, y_1)$.\n\nFor each testcase, output a single line consisting of the number of stars on the segment.\n\nIn the first testcase, the only covered star is $(1, 1)$.\n\nIn the second testcase, the covered stars are $(1, 2), (2, 4), (3, 6)$.\n\n"},{"iden":"input","content":"The first line contains a positive integer $T$ ($T <= 100$), the number of testcases.Each testcase contains 4 integers $x_0, y_0, x_1, y_1$ ($| x_i | <= 10^9$ and $| y_i | <= 10^9$ for $i = 0, 1$), representing the segment $(x_0, y_0)$ to $(x_1, y_1)$."},{"iden":"output","content":"For each testcase, output a single line consisting of the number of stars on the segment."},{"iden":"note","content":"In the first testcase, the only covered star is $(1, 1)$.In the second testcase, the covered stars are $(1, 2), (2, 4), (3, 6)$."}],"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\\} $, let $ P_k = (x_0^{(k)}, y_0^{(k)}) $ and $ Q_k = (x_1^{(k)}, y_1^{(k)}) $ be the endpoints of a line segment in $ \\mathbb{Z}^2 $.\n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. $ |x_i^{(k)}| \\le 10^9 $, $ |y_i^{(k)}| \\le 10^9 $ for $ i \\in \\{0,1\\} $, $ k \\in \\{1, \\dots, T\\} $\n\n**Objective**  \nFor each test case $ k $, compute the number of lattice points (stars) on the closed line segment from $ P_k $ to $ Q_k $:  \n$$\n\\gcd(|x_1^{(k)} - x_0^{(k)}|, |y_1^{(k)} - y_0^{(k)}|) + 1\n$$","simple_statement":"Given two points with integer coordinates, count how many integer-coordinate points (stars) lie on the straight line segment between them.","has_page_source":false}