_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck._
Singhal has a string $S$ consisting of lowercase English letters. He wants to form lexicographical smallest string by applying a operation atmost once.
Operation is —
Choose three distinct indices $i_1, i_2, i_3$ such that $1 <= i_i < i_2 < i_3 <= | S |$, where $| S |$ is the length of string and perform cyclic right shift on these indices.
If value at $i_1, i_2, i_3$ is $s_1, s_2, s_3$, then after performing right cyclic shift on these indices, value at indices will change to $i_2 arrow.r s_1, i_3 arrow.r s_2, i_1 arrow.r s_3$.
Example - $S =$ "codedigger". Chosen indices is $1, 2, 3$ then resultant string will be $S =$ "dcoedigger".
A string a is lexicographical smaller than a string b if and only if one of the following holds:
The first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.
Each query contains a string $S (1 <= | S | <= 10^5)$ consisting of lowercase English letters. $| S |$ is the length of the string.
It is guaranteed that the total sum of $| S |$ is at most $10^5$.
Print $t$ answers to the test cases. Each answer must be consisting of single lexicographical smallest possible string.
In the first query, apply right cyclic shift on indices $1, 2, 3$ to get the smallest possible string $S =$ _aab_.
In the second or third query , if we apply operation we get lexicographical larger string. So we will not apply any operation.
## Input
The first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.Each query contains a string $S (1 <= | S | <= 10^5)$ consisting of lowercase English letters. $| S |$ is the length of the string.It is guaranteed that the total sum of $| S |$ is at most $10^5$.
## Output
Print $t$ answers to the test cases. Each answer must be consisting of single lexicographical smallest possible string.
[samples]
## Note
In the first query, apply right cyclic shift on indices $1, 2, 3$ to get the smallest possible string $S =$ _aab_.In the second or third query , if we apply operation we get lexicographical larger string. So we will not apply any operation.
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of sequences.
Let $ S_n $ be the set of all $ n $-holy sequences (defined as all sequences of length $ n $ with elements in $ \{1, 2, \dots, n\} $).
For a sequence $ p \in S_n $ and $ t \in \{1, 2, \dots, n\} $, let $ \mathrm{cnt}(p, t) $ denote the number of occurrences of $ t $ in $ p $.
**Constraints**
1. $ 1 \leq n \leq 3000 $
2. $ 1 \leq m \leq 10^9 $
3. Total sum of $ n $ across test cases $ \leq 10^4 $
**Objective**
For each $ t \in \{1, 2, \dots, n\} $, compute:
$$
\sum_{p \in S_n} \mathrm{cnt}(p, t)^2 \mod m
$$
Output the result for each $ t = 1 $ to $ n $.