{"raw_statement":[{"iden":"statement","content":"This problem is very simple so the problem setters decided that its statement should be simple too. You are given two integers $n$ and $m$ such that $\"gcd\"(n, thin m) equiv 1$, and your task is to find the value of the function $\"F\"(n, thin m)$ as follows: \n\nIn mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For example, the gcd of $8$ and $12$ is $4$.\n\nThe first line contains an integer $T$ ($1 <= T <= 10^5$) specifying the number of test cases.\n\nEach test case consists of a single line contains two integers $n$ and $m$ ($1 <= n, m <= 10^9, thin \"gcd\"(n, thin m) equiv 1$).\n\nFor each test case, print a single line containing the value of the function $\"F\"(n, thin m)$ as described in the statement.\n\nIn the first test case, the value of the function can be found as follow: $$\\text{F}(2,\\,3) = \\text{gcd}(5^2 + 7^2,\\,5^3 + 7^3)$$ $$\\text{F}(2,\\,3) = \\text{gcd}(74,\\, 468)$$ $$\\text{F}(2,\\,3) = 2$$\n\nIn the second test case, the value of the function can be found as follow: $$\\text{F}(5,\\,3) = \\text{gcd}(5^5 + 7^5,\\,5^3 + 7^3)$$ $$\\text{F}(5,\\,3) = \\text{gcd}(19932,\\, 468)$$ $$\\text{F}(5,\\,3) = 12$$\n\n"},{"iden":"input","content":"The first line contains an integer $T$ ($1 <= T <= 10^5$) specifying the number of test cases.Each test case consists of a single line contains two integers $n$ and $m$ ($1 <= n, m <= 10^9, thin \"gcd\"(n, thin m) equiv 1$)."},{"iden":"output","content":"For each test case, print a single line containing the value of the function $\"F\"(n, thin m)$ as described in the statement."},{"iden":"note","content":"In the first test case, the value of the function can be found as follow: $$\\text{F}(2,\\,3) = \\text{gcd}(5^2 + 7^2,\\,5^3 + 7^3)$$ $$\\text{F}(2,\\,3) = \\text{gcd}(74,\\, 468)$$ $$\\text{F}(2,\\,3) = 2$$In the second test case, the value of the function can be found as follow: $$\\text{F}(5,\\,3) = \\text{gcd}(5^5 + 7^5,\\,5^3 + 7^3)$$ $$\\text{F}(5,\\,3) = \\text{gcd}(19932,\\, 468)$$ $$\\text{F}(5,\\,3) = 12$$"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the size of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $.  \n\n**Operation Definition**  \nFor a segment $ [L, R] $, the separation operation $ S(L, R) $ reorders the subarray $ (a_L, a_{L+1}, \\dots, a_R) $ as follows:  \n- Extract elements at odd offsets from $ L $: $ a_{L+1}, a_{L+3}, a_{L+5}, \\dots $ (i.e., indices $ i $ where $ i - L $ is odd), preserving their relative order.  \n- Append elements at even offsets from $ L $: $ a_L, a_{L+2}, a_{L+4}, \\dots $ (i.e., indices $ i $ where $ i - L $ is even), preserving their relative order.  \nThe result replaces the original segment.\n\n**Constraints**  \n1. $ 1 \\le n \\le 3000 $  \n2. $ a_i \\in \\{1, 2, \\dots, n\\} $, all distinct  \n3. Use at most $ 15000 $ separation operations  \n\n**Objective**  \nFind a sequence of operations $ S(L_1, R_1), S(L_2, R_2), \\dots, S(L_k, R_k) $ with $ 0 \\le k \\le 15000 $, such that applying them in order transforms $ A $ into the sorted array $ (1, 2, \\dots, n) $.","simple_statement":"Given an array of distinct numbers from 1 to n, sort it in ascending order using at most 15,000 separation operations.  \n\nA separation operation S(L, R) rearranges the segment from index L to R by:  \n- First taking all elements at odd positions relative to L (i.e., L+1, L+3, ...), in order.  \n- Then taking all elements at even positions relative to L (i.e., L, L+2, ...), in order.  \n\nOutput any sequence of operations (each defined by L and R) that sorts the array. You don’t need to minimize the number of operations.","has_page_source":false}