8572: Regular expression

链接：https://ac.nowcoder.com/acm/contest/33192/G
来源：牛客网
Grammy has recently been interested in regular expression while focusing on cases where the alphabet consists of characters from $a$ to $z$. Today she asks NIO some questions. Each question gives string $A$, asking the minimum length of expressions matching string $A$ according to the matching rules and the number of all shortest expressions.

To learn detailed rules about how regular expressions match strings,
you can refer to https://en.wikipedia.org/wiki/Regular_expression.

Here we only consider characters from 'a' to 'z', '.', '?', '*', '+', '|', '(', ')'. It is assumed that the asterisk, the question mark and the plus sign have the highest priority, then concatenation and then alternation. Parentheses can be used to change the priority. For example, $\text{a(b|c)}$ can match “ab” and “ac”. If there is no ambiguity then parentheses may be omitted. For example, $\text{(ab)c}$ can be written as $\text{abc}$, and $\text{a|(b(c*))}$ can be written as $\text{a|bc*}$

Here are some examples of matching:

• (or): $\text{gray|grey}$ can match “gray” or “grey”.
  
  
• (question mark): $\text{colou?r}$ matches both “color” and “colour”.
  
  
• (asterisk): $\text{ab*c}$ matches “ac”, “abc”, “abbc”, “abbbc”, and so on.
  
  
• (plus sign): $\text{ab+c}$ matches “abc”, “abbc”, “abbbc”, and so on, but not “ac”.
  
  
• (wildcard): $\text{a.b}$ matches any string that contains an “a”, and then any character and then “b”; and $\text{a.*b}$ matches any string that contains an “a”, and then the character “b” at some later point. More precisely, “ab” can be matched by $\text{a.*b}$ but not $\text{a.b}$.
  
  
• (concatenation): Let expression R=(ab|c)R=\texttt{(ab|c)}R=(ab|c) matches $\{ab,c\}$ and expression S=(d|ef)S=\texttt{(d|ef)}S=(d|ef) matches {d,ef}\{d, ef\}{d,ef}. Then, (RS)=((ab|c)(d|ef))(RS)=\texttt{((ab|c)(d|ef))}(RS)=((ab|c)(d|ef)) matches {abd,abef,cd,cef}\{abd, abef, cd, cef\}{abd,abef,cd,cef}
  

If you are not sure about whether a regular expression is valid, then you can use https://regex101.com/ to check its validity. Note that the character set we use is slightly different from the website. 

The input contains only a single case.
The first line contains a single integer $Q$ ($1\le Q\le 100000$), denoting the number of questions. The $i$-th line of the following $Q$ lines contain one string $A$ consisting of lowercase letters ($1\le |A|\le 200000$), denoting the string $A$ of the $i$-th question. It is guaranteed that ∑∣A∣≤1000000\sum |A|\leq 1\,000\,000∑∣A∣≤1000000.

For each question, output a single line containing 2 integers - the minimum length and the number to the question. Note that the answer may be extremely large, so please print it modulo $998244353$ instead.