Did you take part in the practice session? If you did, you will be able to read this problem statement faster. But if you missed the practice session, don’t worry, we will tell you all you need to know.
One of the practice tasks was the task Rearranged alphabet. In this task we asked the contestants to find a short string of lowercase letters such that each of the 26! permutations of a through z occurs in it as a (not necessarily contiguous) subsequence. For example, if the alphabet only consisted of a, b, and c, abcabac would be a valid answer, but abccba would not (both bac and cab is missing).
Solving the practice task was simple enough: you just have to find a pattern and print the corresponding string. On the other hand, grading the practice task is much more complicated: you have to read a string and check whether it actually contains all possible permutations.
Preparing the grader for the practice problem was quite fun. In fact, it was so much fun that we wanted to share it with you.
Problem specification
You are given a string of lowercase English letters.
In the easy subproblem D1, check whether each of 26! permutations of a through z occurs in the string as a subsequence.
In the hard subproblem D2, count the number of permutations of a through z that do not occur in the given string as a subsequence. As this number may be quite big, output it modulo 65521.
Input specification
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of a single line containing a nonempty string of lowercase English letters.
In the easy subproblem D1, t ≤ 150 and none of the strings is longer than 2500 characters.
In the hard subproblem D2, t ≤ 20 and the sum of lengths of all strings
does not exceed 1000.
Output specification
For each test case, output a single line with the answer.
That is, in the easy subproblem D1, output “YES” (without quotes) if the given string contains all permutations, or “NO” if it doesn’t.
In the hard subproblem D2, output the number of missing permutations modulo 65521.
Example
In D2, note that 26! mod 65521 = 8297.