Andeviking and Bob

描述

Andeviking 和 Bob 准备玩一个字符串游戏，规则如下：

系统给定一个由小写字母组成的字符串 $S$，令这个字符串所有本质不同的子串组成的集合为 $A$。

Andeviking 和 Bob 面前各有一个盒子，他们轮流从集合中拿取字符串放入自己面前的盒子中并从对方处获得或向对方支付一定数量的金币，当集合为空时，游戏结束。初始两人金币数量都为 0，具体金币分配规则如下：

假设此次操作的人为 Bob，他选择了集合中的一个字符串 $t$。

首先，Bob会立刻得到来自系统奖励的 $2\times|t|$（$|t|$代表字符串$t$的长度）个金币。令Andeviking面前的盒子中以 $t$ 为前缀的字符串个数为 $n_1$，是 $t$ 的前缀的字符串个数为 $n_2$。若 $n_1 > n_2$，则 Andeviking 将要支付$n_1-n_2$个金币给 Bob，若 $n_1<n_2$，则 Bob 将要支付$n_2-n_1$个金币给 Andeviking，若 $n_1=n_2$则无事发生。

Andeviking 与 Bob 都是老奸巨猾的人，他们都希望自己能够获得尽可能多的金币，其中 Andeviking 先手操作。可以证明，当两人都采用最佳策略时，最终的结局是唯一的。请你预测一下在二者都采用最佳策略的情况下游戏结束时二者的金币数量吧！

为了避免歧义，接下来将对特殊名词进行定义。

子串是指字符串 $S$ 通过删除开头与最后几个字符（可以为0个）得到的字符串。例如 "abcd", "bcde", "abcdef" 是 "abcdef" 的子串，而 "acd", "dbc" 不是 "abcdef" 的子串。

两个字符串本质不同，当且仅当二者长度不同或存在一个位置 $i$，使得 $a_i\not= b_i$。

对于一个集合 $A$，$A$ 中的元素两两不同，不可重复。

注意：在游戏过程中允许欠费，也就是说允许金币数为负数。

输入数据

本题采用多测

第一行一个正整数 $T$，代表数据组数

每组数据包含一行，为一个字符串 $S_i$ 代表每组数据中系统给定的字符串

输入数据保证：

$T \leq 5\times 10^4$

$|S_i| \leq 5\times10^5$

$\sum^T_{i=1}|S_i| \leq 10^6$

字符串由小写字母构成

输出数据

共 $T$ 行，每行两个整数，分别代表 Andeviking 与 Bob 的最终金币数量，两个整数之间以空格分隔。

样例输入

2
a
ab

样例输出

2 0
5 3

样例解释

第一组测试： 字符串 S 为 "a" ，集合 A 中只有字符串 "a" Andeviking 选择字符串 "a"，获得来自系统的 2 个金币，游戏结束。 最终答案为 2 0

第二组测试： 字符串 S 为 "ab"，集合 A 中有三个元素，分别为 {"a","b","ab"} Andeviking 选择字符串 "ab"，获得来自系统的 4 个金币。Bob 选择字符串 "a"，获得来自系统的2个金币，由于 "a" 是 "ab" 的前缀，因此 Andeviking 向 Bob 支付1个金币。Andeviking 最后选择字符串 "b"，获得来自系统的2个金币。 最终答案为 5 3