#8258. 「JXOI Round 1」T4 二进制 普及/提高−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: jxy2012

题目描述

给定 个整数

对于整数 ,设它在二进制下为 的位分别为 ,那么它的权值 。此处的二进制位的编号从右到左,依次为 。其中 表示 按位异或 符号。

你想要知道有多少个 使得 。为了方便,请你用 二进制形式 输出答案(不取模)。

请注意:输出不能包含前导 ,除非答案为

输入格式

本题有多组测试数据。

第一行输入一个整数 ,表示测试数据组数。

接下来依次输入每组测试数据。对于每组测试数据:

  • 第一行输入一个正整数
  • 第二行输入 个整数

输出格式

对于每组数据,输出一行一个二进制整数,表示答案。

再次提示:输出不能包含前导 ,除非答案为

样例

样例输入

5
2
0 1 2
3
1 3 3 1
4
2 2 5 4 2
5
7 0 3 4 0 1
6
5 2 1 8 6 0 9

样例输出

10
1
100
11
0

数据范围与提示

「样例解释 #1」

对于第 组数据,

  • ,所以
  • ,所以
  • ,所以
  • ,所以
  • ,所以

这其中有 ,所以输出

「数据范围」

表示单个测试点中 的和。

对于所有数据,