给定一个字符串 $s$，其子串 $s[L..R]$ 的 jingle $J(L, R)$ 定义为该子串中出现的所有字符构成的集合。例如，如果 $s = \text{"abacaba"}$，那么 $s[3..5] = \text{"aca"}$ 且 $J(3, 5) = \{a, c\}$。

给定一个字符串 $s$。求其所有非空子串的所有可能 jingle，并对于每个可能的 jingle，求出以该 jingle 为其字符集合的 $s$ 的最长子串。

在上述例子中，有 6 个集合作为 $s$ 的子串的 jingle 出现。例如，对于集合 $\{a, b\}$，有六个子串具有该 jingle：$s[1..2]$、$s[1..3]$、$s[2..3]$、$s[5..6]$、$s[5..7]$ 和 $s[6..7]$。其中 $s[1..3]$（以及 $s[5..7]$）的长度为 3，这是具有该 jingle 的 $s$ 的最长子串。

由于输出所有的 jingle 会使输出文件过大，你只需要输出以下总和：

$$v(s) = \sum_{J \in \mathbb{J}} S(J)L(J)$$

这里 $\mathbb{J}$ 是该字符串的所有 jingle 构成的集合，$S(J)$ 是 $J$ 中的字符数量，$L(J)$ 是以 $J$ 为其 jingle 的 $s$ 的最长子串的长度。

输入格式

输入包含多组测试数据。

第一行包含一个整数 $t$ — 测试数据的组数。

接下来的 $t$ 行，每行包含一个由最多 $100\,000$ 个小写字母组成的字符串 $s$。

输入中所有测试数据的字符串长度之和不超过 $100\,000$。

输出格式

对于每组测试数据，输出两个整数：$d$ — 作为 $s$ 的某些子串的 jingle 出现的不同集合的数量，以及 $v(s)$ — 题目描述中所述的总和。

样例

输入样例 1

2
abacaba
abbcccdddd

输出样例 1

6 36
10 125