Grammy has recently been interested in regular expression while focusing on cases where the alphabet consists of characters from to . Today she asks NIO some questions. Each question gives string , asking the minimum length of expressions matching string 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, can match “ab” and “ac”. If there is no ambiguity then parentheses may be omitted. For example, can be written as , and can be written as

Here are some examples of matching:

• (or): can match “gray” or “grey”.
  
  
• (question mark): matches both “color” and “colour”.
  
  
• (asterisk): matches “ac”, “abc”, “abbc”, “abbbc”, and so on.
  
  
• (plus sign): matches “abc”, “abbc”, “abbbc”, and so on, but not “ac”.
  
  
• (wildcard): matches any string that contains an “a”, and then any character and then “b”; and matches any string that contains an “a”, and then the character “b” at some later point. More precisely, “ab” can be matched by but not .
  
  
• (concatenation): Let expression matches and expression matches . Then, matches