Grammy 最近对正则表达式产生了兴趣，并专注于字母表由 'a' 到 'z' 组成的字符集的情况。今天她向 NIO 提出了几个问题。每个问题给出一个字符串 $A$，要求计算根据匹配规则能够匹配字符串 $A$ 的正则表达式的最小长度，以及该长度下此类表达式的数量。

关于正则表达式如何匹配字符串的详细规则，可以参考 https://en.wikipedia.org/wiki/Regular_expression。

这里我们仅考虑 'a' 到 'z' 的字符以及特殊字符 '.'、'?'、''、'+'、'|'、'('、')'。假设星号、问号和加号具有最高优先级，其次是连接，最后是选择。括号可用于改变优先级。例如，“a(b|c)” 可以匹配 “ab” 和 “ac”。当括号不改变优先级时可以省略。例如，“(ab)c” 可以写成 “abc”，“a|(b(c))” 可以写成 “a|bc*”。

以下是一些匹配示例：

• (或)："gray|grey" 可以匹配 "gray" 或 "grey"。
• (问号)："colou?r" 同时匹配 "color" 和 "colour"。
• (星号)："ab*c" 匹配 "ac"、"abc"、"abbc"、"abbbc" 等。
• (加号)："ab+c" 匹配 "abc"、"abbc"、"abbbc" 等，但不匹配 "ac"。
• (通配符)："a.b" 匹配任何包含 "a"，后跟任意单个字符，再后跟 "b" 的字符串；"a.b" 匹配任何包含 "a"，并在之后某个位置包含字符 "b" 的字符串。更准确地说，"ab" 可以被 "a.b" 匹配，但不能被 "a.b" 匹配。
• (连接)：考虑表达式 $R = \text{"(ab|c)"}$ 匹配集合 {"ab", "c"}，表达式 $S = \text{"(d|ef)"}$ 匹配集合 {"d", "ef"}。那么，$(RS) = \text{"((ab|c)(d|ef))"}$ 匹配集合 {"abd", "abef", "cd", "cef"}。

输入格式

输入仅包含一组数据。 第一行包含一个整数 $Q$ ($1 \le Q \le 100\,000$)，表示问题的数量。接下来的 $Q$ 行，每行包含一个由小写英文字母组成的字符串 $A$ ($1 \le |A| \le 200\,000$)，表示第 $i$ 个问题的字符串 $A$。保证 $\sum |A| \le 1\,000\,000$。

输出格式

对于每个问题，输出一行，包含两个整数：匹配表达式的最小长度，以及该长度下匹配表达式的数量。注意答案可能非常大，请对 998 244 353 取模。

样例

输入 1

2
a
ab

输出 1

1 2
2 6