{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYou are given an array of integers $$$a$$$ of size $$$n$$$. You can choose a set of non-overlapping subarrays of the given array (note that some elements may be not included in any subarray, this is allowed). For each selected subarray, calculate the MEX of its elements, and then calculate the \u003ca href\u003d\"https://en.wikipedia.org/wiki/Bitwise_operation#XOR\"\u003ebitwise XOR\u003c/a\u003e of all the obtained MEX values. What is the maximum bitwise XOR that can be obtained?\u003c/p\u003e\u003cp\u003eThe MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance: \u003c/p\u003e\u003cul\u003e \u003cli\u003e The MEX of $$$[2,2,1]$$$ is $$$0$$$, because $$$0$$$ does not belong to the array. \u003c/li\u003e\u003cli\u003e The MEX of $$$[3,1,0,1]$$$ is $$$2$$$, because $$$0$$$ and $$$1$$$ belong to the array, but $$$2$$$ does not. \u003c/li\u003e\u003cli\u003e The MEX of $$$[0,3,1,2]$$$ is $$$4$$$, because $$$0$$$, $$$1$$$, $$$2$$$ and $$$3$$$ belong to the array, but $$$4$$$ does not. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer $$$t$$$ ($$$1 \\leq t \\leq 5000$$$) — the number of test cases. This is followed by the description of the test cases.\u003c/p\u003e\u003cp\u003eThe first line of each test case contains an integer $$$n$$$ ($$$1 \\leq n \\leq 5000$$$) — the size of the array $$$a$$$.\u003c/p\u003e\u003cp\u003eThe second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \\ldots, a_n$$$ ($$$0 \\leq a_i \\leq n$$$) — the array $$$a$$$.\u003c/p\u003e\u003cp\u003eIt is guaranteed that the sum of all $$$n$$$ values across all test cases does not exceed $$$5000$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output a single number — the maximum possible XOR of the MEX values of the selected subarrays.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n2\n1 0\n10\n1 2 0 7 1 2 0 2 4 3\n10\n2 1 0 7 1 2 0 2 4 3\n3\n1 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n6\n7\n0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case, the maximum XOR is $$$2$$$ if we take the entire array, $$$\\operatorname{MEX}([1, 0]) \u003d 2$$$.\u003c/p\u003e\u003cp\u003eIn the second test case, the maximum XOR is $$$6$$$ if we partition the array into segments $$$[1, 2, 0]$$$ and $$$[7, 1, 2, 0, 2, 4, 3]$$$: \u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$\\operatorname{MEX}([1, 2, 0]) \u003d 3$$$, \u003c/li\u003e\u003cli\u003e $$$\\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) \u003d 5$$$, \u003c/li\u003e\u003c/ul\u003e therefore, the XOR is $$$5 \\oplus 3\u003d6$$$.\u003cp\u003eIn the third test case, the maximum XOR is $$$7$$$ if we partition the array into segments $$$[1, 0]$$$ and $$$[7, 1, 2, 0, 2, 4, 3]$$$: \u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$\\operatorname{MEX}([1, 0]) \u003d 2$$$, \u003c/li\u003e\u003cli\u003e $$$\\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) \u003d 5$$$, \u003c/li\u003e\u003c/ul\u003e therefore, the XOR is $$$5 \\oplus 2 \u003d 7$$$."}}]}