{"raw_statement":[{"iden":"statement","content":"Dwik and his brother Samir both received scholarships from a famous university in India. Their father, Besher, wants to send some money with each of them.\n\nBesher has n coins, the ith coin has a value of ai. He will distribute these coins between his two sons in n steps. In the ith step, he chooses whether to give the ith coin to Dwik or to Samir.\n\nLet xi be the absolute difference between the sum of Dwik's and Samir's coins after the ith step. The unfairness factor of a distribution is max({x1, x2, ..., xn}). Besher wants to minimize the unfairness factor, can you help him?\n\nThe first line of the input consists of a single integer t, the number of test cases. Each test case consists of 2 lines: \n\nThe first line contains an integer n (1 ≤ n ≤ 100). \n\nThe second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100).\n\nPrint t lines, ith line containing a single integer, the answer to the ith test case.\n\nIn the first sample test, besher has 5 coins (1, 2, 1, 4, 3), he can distribute them in the following way: \n\n *Step 1:* Give the first coin to dwik , d = 1, s = 0  x1 = |1 - 0| = 1 \n\n *Step 2:* Give the second coin to samir, d = 1, s = 2  x2 = |1 - 2| = 1 \n\n *Step 3:* Give the third coin to samir, d = 1, s = 3  x3 = |1 - 3| = 2 \n\n *Step 4:* Give the fourth coin to dwik, d = 5, s = 3  x4 = |5 - 3| = 2 \n\n *Step 5:* Give the fifth coin to samir, d = 5, s = 6  x5 = |5 - 6| = 1 \n\n max({x1, x2, x3, x4, x5}) = 2\n\n"},{"iden":"input","content":"The first line of the input consists of a single integer t, the number of test cases. Each test case consists of 2 lines: The first line contains an integer n (1 ≤ n ≤ 100). The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100)."},{"iden":"output","content":"Print t lines, ith line containing a single integer, the answer to the ith test case."},{"iden":"note","content":"In the first sample test, besher has 5 coins (1, 2, 1, 4, 3), he can distribute them in the following way:  *Step 1:* Give the first coin to dwik , d = 1, s = 0  x1 = |1 - 0| = 1  *Step 2:* Give the second coin to samir, d = 1, s = 2  x2 = |1 - 2| = 1  *Step 3:* Give the third coin to samir, d = 1, s = 3  x3 = |1 - 3| = 2  *Step 4:* Give the fourth coin to dwik, d = 5, s = 3  x4 = |5 - 3| = 2  *Step 5:* Give the fifth coin to samir, d = 5, s = 6  x5 = |5 - 6| = 1  max({x1, x2, x3, x4, x5}) = 2"}],"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\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ be the total number of people in the line.  \n- Let $ i_k \\in \\mathbb{Z} $ be the initial position (1-indexed) of the coach.  \n\nThe metal detector activates alternately: person $ j $ activates it if $ j $ is even, and does not activate it if $ j $ is odd.  \nPeople who activate the detector are sent to the end of the line.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. $ 1 \\le N_k \\le 10^9 $  \n3. $ 1 \\le i_k \\le N_k $  \n\n**Objective**  \nFor each test case $ k $, determine the order $ j_k $ in which the coach passes through the detector **without activating it**, i.e., the $ j_k $-th person to successfully pass (on an odd-numbered turn in the filtered sequence).","simple_statement":"The coach is in a line of N people. A broken metal detector activates on every second person (2nd, 4th, 6th, ...). People who activate it are sent to the end of the line. The coach wants to know: when will he be the j-th person to pass through without activating the detector?","has_page_source":false}