题目描述

一个由 $k$ 个非负整数 $a_1,a_2,\cdots,a_k$ 构成的可重集 $S=\{a_1,a_2,\cdots ,a_k\}$，定义其权值为 $a_1\oplus a_2 \oplus a_3 \oplus \cdots \oplus a_k$。其中，$\oplus$ 表示按位异或。特殊的，空集 $\varnothing$ 的权值为 $0$。

在可重集 $S=\{a_1,a_2,\cdots,a_k\}$ 上，寅丸星和娜兹琳轮流进行游戏，寅丸星先手，每人依次进行一次操作。设当前可重集为 $S$，定义一次操作为：

• 选择一个元素 $a_i \in S$，将 $S$ 中的元素 $a_i$ 删除。若 $S=\{a_1,a_2, \cdots ,a_m\}$，操作即令 $S \leftarrow \{a_1,a_2, \cdots,a_{i−1},a_{i+1},a_{i+2},\cdots,a_m\}$。

在任意时刻，若 $S$ 的权值为 $0$，则游戏立刻停止，最后一次进行操作的人失败。若最后一次无人进行操作，即初始时权值为 $0$，则寅丸星失败。

给定一个长度为 $n$ 的非负整数数组 $x_1,x_2,\cdots x_n$。寅丸星和娜兹琳对每一个不同的区间 $[l,r]$（$l,r\in ℤ$ 且 $1\le l \le r \le n$），在区间内的所有数构成的可重集 $S=\{x_l,x_{l+1},\cdots,x_r\}$ 上都进行了一次游戏。假设寅丸星和娜兹琳采用最优策略，求寅丸星获胜的数量和娜兹琳获胜的数量。

输入格式

输入的第一行包含一个整数 $t$（$1\le t \le 100$），表示测试用例的数量。

接下来是 $t$ 个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）。

每个测试用例的第二行包含 $n$ 个非负整数 $x_1,x_2, \cdots,x_n（0 \le x_i \le 2 \times 10^5$），表示给定数组中的元素。

保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$。

输出格式

对于每个测试用例，输出一行，包含二个整数，分别表示寅丸星获胜的数量和娜兹琳获胜的数量。

样例

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

0 1
1 5
3 7
8 13
39 52

样例解释

在样例测试用例 2 中，若在区间 $[1,2]$ 内的所有数构成的可重集 $S=\{5,5\}$ 上进行游戏，初始权值为 $5 \oplus 5=0$，游戏立刻停止，最后一次无人进行操作，寅丸星失败，娜兹琳获胜。

若在区间 $[2,3]$ 内的所有数构成的可重集 $S=\{5,2\}$ 上进行游戏，初始权值为 $5 \oplus 2=7$。寅丸星可以选择将 $2$ 删除，此刻 $S=\{5\}$，权值为 $5$。随后，娜兹琳只能选择将 $5$ 删除，此刻 $S= \varnothing$，权值为 $0$，游戏立刻停止，最后一次娜兹琳进行操作，娜兹琳失败，寅丸星获胜。

对于在样例测试用例 2，寅丸星在区间 $[2,3]$ 内的所有数构成的可重集上获胜，娜兹琳在区间 $[1,1]$、$[1,2]$、$[1,3]$、$[2,2]$、$[3,3]$ 内的所有数构成的可重集上获胜。