题目描述

题目背景

『生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。』

『云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。』

——《追忆》，2025 省选联考

圣辇船，正以平稳的速度航行在无垠的云海之上。云朵如同蓬松的棉絮，在船舷两侧缓缓后退，阳光毫无阻碍地洒在甲板上，将一切都镀上一层金色。村纱水蜜船长哼着不知名但旋律悠扬的船歌，灵巧地调整着几面巨大风帆的角度，让船乘上最合适的气流。风拂过她海蓝色的头发，带着高空特有的自由气息。

云居一轮则放松地靠在船舷边，眺望着远方如岛屿般悬浮的云山。她巨大的式神“云山”，像一团真正温顺而蓬松的云朵，静静地漂浮在她身旁，偶尔会伸出一小缕“云丝”，好奇地碰碰一轮的发梢或衣角。一轮只是微笑着，任由它嬉戏。

甲板中央，寅丸星盘膝而坐，膝上横放着那尊闪烁微光的宝塔。她正用一块柔软的绒布，极其细致地擦拭着塔身，动作轻柔得像在对待初生的婴儿。每一道纹路，每一个棱角，都被擦拭得熠熠生辉。宝塔的光芒似乎随着她的擦拭，变得更加温润内敛。

而在她旁边，娜兹琳正清点着今天收集到的“飞宝”——那些闪闪发光的、蕴含奇妙力量的宝物。她拿着一个小本子，嘴里念念有词：“发光勾玉三枚，星型碎晶五块，浮空羽毛两根……嗯，成色都不错。”不过，她的目光时不时会瞟向寅丸星手中的宝塔，以及宝塔周围。那些闪亮的东西，总是容易吸引她那些淘气的“老鼠”朋友们的注意，得提前规划好防守（或者说驱赶）路线才行。

圣辇船就这样，载着它的船员和宝物，在蓝天与云海之间，进行着一场宁静而充满希望的航行。目标是下一个收集点，也是下一片未知的风景。

题目描述

一个由 \(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 \mathbb{Z}\) 且 \(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]\) 内的所有数构成的可重集上获胜。