#3175. J-PSC 加密(decrypt)by 俊鹏

J-PSC 加密(decrypt)by 俊鹏

题目描述

小 H 最近爱上了密码学,他最近正在研究一种叫做 J-PSC 的密码系统。这种密码的明文由 nn 个非负数字 aa 组成,密文是 3131 个非负整数,分别是 x1,x2,,x31x_1,x_2,\cdots,x_{31}。对于一组明文,其密文是明文每一位二进制为 11 的总个数。例如,当 n=2n=2,明文是 373373905905 时,373373 的二进制是 (00101110101)2(00101110101)_2905905 的二进制是 (01110001001)2(01110001001)_2,因此有 x1=2,x2=0,x3x8=1,x9=2,x10=1,x11x31=0x_1=2,x_2=0,x_3\sim x_8=1,x_9=2,x_{10}=1,x_{11}\sim x_{31}=0

现在,小 H 给了你几组明文,他请你帮他将其加密。

输入格式

第一行一个正整数 TT,表示明文组数。

接下来对于每一组数据,第一行一个正整数 nn,表示明文个数;第二行有 nn 个非负整数,表示明文。

输出格式

对于每组数据,因为小 H 讨厌过多的输出,你需要输出 i=131xi\bigoplus_{i=1}^{31} x_i,其中 \bigoplus 为按位异或操作。

样例 #1

样例输入 #1

2
2
373 905
4
9823478 12783872 98437 863545

样例输出 #1

1
6

样例 #2

样例输入 #2

2
5
1 2 3 4 5
10
972589726 92857162 472815263 715264734 46371827 46372819 19504738 90201873 27362517 839201735

样例输出 #2

3
3

提示

对所有数据:T1000,n107T\le1000,\sum n\le10^7