题目描述

给定一个长度为 $n$ 的非负整数序列 $a_1, a_2, \ldots, a_n$，统计有多少对 $(i, j)$ 满足 $1 \leq i \leq j \leq n$ 并且 $a_i \oplus a_j$ 在十进制表示下是回文的，其中 $\oplus$ 表示按位异或操作。

例如，$13 \oplus 27 = 22$，由于 $22$ 从左到右读和从右到左读得到的字符串相同，因此 $22$ 是一个回文数。

输入格式

第一行一个整数 $T$ 表示数据组数。对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个非负整数 $a_{1\sim n}$。

输出格式

对于每组数据，输出一行一个整数表示答案。

2
4
13 27 12 26
3
2 2 2

8
6

样例解释 1

在第一组数据中，13 xor 13 = 0, 13 xor 27 = 22, 13 xor 12 = 1, 27 xor 27 = 0, 27 xor 26 = 0, 12 xor 12 = 0, 12 xor 26 = 22, 26 xor 26 = 0，共 8 对符合题意的 (i, j)。 在第二组数据中，任意的 1 <= i <= j <= n 都是符合题意的，共 6 对。

数据范围

对于 $30\%$ 的数据，$1\leq \sum n\leq 1000$，$0\leq a_i<2^{10}$。

对于 $60\%$ 的数据，$1\leq \sum n\leq 2\times 10^5$，$0\leq a_i<2^{10}$。

对于 $100\%$ 的数据，$1\leq T\leq 100$，$1\leq n\leq 10^5$，$1\leq \sum n\leq 2\times 10^5$，$0\leq a_i<2^{15}$。