{"raw_statement":[{"iden":"statement","content":"给定 $n + 1$ 个整数 $a_0\\dots a_n$。\n\n对于整数 $u$，设它在二进制下为 $1$ 的位分别为 $k_1, k_2\\dots k_m$，那么它的权值 $f(u) = a_{k_1} \\oplus a_{k_2} \\oplus \\dots \\oplus a_{k_m}$。此处的二进制位的编号从右到左，依次为 $0,1,2\\dots$。其中 $\\oplus$ 表示 [按位异或](https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fromModule=search-result_lemma-recommend) 符号。\n\n你想要知道有多少个 $0 \\leq u \\leq 2^n - 1$ 使得 $f(u) = f(u + 1)$。为了方便，请你用 **二进制形式** 输出答案（不取模）。\n\n请注意：输出不能包含前导 $0$，除非答案为 $0$。"},{"iden":"input","content":"**本题有多组测试数据。**\n\n第一行输入一个整数 $T$，表示测试数据组数。\n\n接下来依次输入每组测试数据。对于每组测试数据：\n\n- 第一行输入一个正整数 $n$。\n- 第二行输入 $n + 1$ 个整数 $a_0 \\dots a_n$。"},{"iden":"output","content":"对于每组数据，输出一行一个二进制整数，表示答案。\n\n再次提示：输出不能包含前导 $0$，除非答案为 $0$。"},{"iden":"note","content":"#### 「样例解释 #1」\n\n对于第 $1$ 组数据，\n\n- $(0)_{10} = (0)_{2}$，所以 $f(0) = 0$；\n- $(1)_{10} = (1)_{2}$，所以 $f(1) = a_0 = 0$；\n- $(2)_{10} = (10)_{2}$，所以 $f(2) = a_1 = 1$；\n- $(3)_{10} = (11)_{2}$，所以 $f(3) = a_0 \\oplus a_1 = 0 \\oplus 1 = 1$；\n- $(4)_{10} = (100)_{2}$，所以 $f(4) = a_2 = 2$。\n\n这其中有 $f(0) = f(1)$，$f(2) = f(3)$，所以输出 $(2)_{10} = (10)_{2}$。\n\n#### 「数据范围」\n\n设 $\\sum n$ 表示单个测试点中 $n$ 的和。\n\n对于所有数据，$1 \\leq T \\leq 10^3$，$1 \\leq n \\leq 2\\times 10^5$，$\\sum n \\leq 6\\times 10^5$，$0 \\leq a_i \\leq 2^{30} - 1$。\n\n**只有你通过本题的所有测试点，你才能获得本题的分数。**"}],"translated_statement":null,"sample_group":[["5\n2\n0 1 2\n3\n1 3 3 1\n4\n2 2 5 4 2\n5\n7 0 3 4 0 1\n6\n5 2 1 8 6 0 9","10\n1\n100\n11\n0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}