Regular Expression

Grammy has recently been interested in regular expressions, focusing on cases where the alphabet consists of the characters 'a' to 'z'. Today she asks NIO some questions. Each question gives a string $A$ and asks for the minimum length of an expression that matches $A$ under the matching rules, and the number of expressions of that minimum length.

To learn the detailed rules for how regular expressions match strings, see https://en.wikipedia.org/wiki/Regular_expression.

This problem only considers the characters 'a' to 'z' and the special characters '.', '?', '*', '+', '|', '(', and ')'. The asterisk, question mark, and plus sign have the highest priority, then concatenation, then alternation. Parentheses change the priority. For example, "a(b|c)" matches "ab" and "ac". Parentheses may be omitted when they do not change the priority. For example, "(ab)c" can be written as "abc", and "a|(b(c*))" can be written as "a|bc*".

Matching examples:

• Alternation: "gray|grey" matches "gray" or "grey".
• Question mark: "colou?r" matches both "color" and "colour".
• Asterisk: "ab*c" matches "ac", "abc", "abbc", "abbbc", and so on.
• Plus sign: "ab+c" matches "abc", "abbc", "abbbc", and so on, but not "ac".
• Wildcard: "a.b" matches an "a", then any single character, then "b". "a.*b" matches an "a", then a "b" at some later point. "ab" matches "a.*b" but not "a.b".
• Concatenation: let $R =$ "(ab|c)", which matches {"ab", "c"}, and $S =$ "(d|ef)", which matches {"d", "ef"}. Then $RS =$ "((ab|c)(d|ef))" matches {"abd", "abef", "cd", "cef"}.

The input has only one test case.

The first line contains an integer $Q$ ($1\leq Q\leq 100\,000$), the number of questions. Each of the next $Q$ lines contains one string $A$ made of lowercase English letters ($1\leq |A|\leq 200\,000$). It is guaranteed that $\sum |A|\leq 1\,000\,000$.

For each question, print one line with two integers. The first is the minimum length of a matching expression, and the second is the number of matching expressions of that length. Print both values modulo $998\,244\,353$, since the answers may be very large.