정규 표현식

Grammy는 최근 정규 표현식에 관심이 많아서, 알파벳이 'a'부터 'z'까지의 문자로 이루어진 경우를 집중해서 보고 있다. 오늘 Grammy는 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 =$ "(ab|c)"는 {"ab", "c"}와 일치하고, $S =$ "(d|ef)"는 {"d", "ef"}와 일치한다. 그러면 $RS =$ "((ab|c)(d|ef))"는 {"abd", "abef", "cd", "cef"}와 일치한다.

입력은 테스트 케이스 하나로만 이루어진다.

첫 번째 줄에 질문의 개수 $Q$ ($1\leq Q\leq 100\,000$)가 주어진다. 이어지는 $Q$개의 줄에는 각각 영문 소문자로 이루어진 문자열 $A$가 한 줄에 하나씩 주어진다 ($1\leq |A|\leq 200\,000$). 모든 문자열 길이의 합은 $\sum |A|\leq 1\,000\,000$을 넘지 않는다.

각 질문마다 한 줄에 두 정수를 출력한다. 첫 번째 정수는 $A$와 일치하는 식의 최소 길이이고, 두 번째 정수는 그 길이를 가진 식의 개수이다. 답이 매우 클 수 있으므로 두 값 모두 $998\,244\,353$으로 나눈 나머지를 출력한다.