# Raging Infernape solution codechef

## Raging Infernape solution codechef

Finally, Ash and Paul are against each other in the tournament. Battle is between Infernape and Electivire. Infernape just turned on his ability named “Blaze”. Now he is fired up. But there is a problem with Infernape’s Blaze. Even though it gives immense power to Infernape but he losses his mind and attacks everyone. To calm him down so that Infernape can use his ability while staying in control, Ash has to complete the following task.

You are given a String SS made up of lowercase English alphabet. For a substring TT of SS, we define powerpower of TT as |X(T)||X(T)|. Where X(T)X(T) is smallest substring of S that has atleast two substrings equal to TT (i.e. MatchCount(X(T),T)>=2MatchCount(X(T),T)>=2). Now you pick a substring of string SS uniformly randomly and you have to print the expected power of the chosen substring. The answer can be represented as a ratio (i.e. PP / QQ) of two positive co-prime numbers PP and Q.Q. You have to print PQ1P∗Q−1 modulo 998244353998244353.

### Input: Raging Infernape solution codechef

• First line will contain TT, number of testcases. Then the testcases follow.
• Each testcase contains a single line of input, a string S.

### Output: Raging Infernape solution codechef

For each testcase, output in a single line the expected power of chosen substring modulo 998244353.

### Constraints Raging Infernape solution codechef

• 1T10001≤T≤1000
• 1|S|1051≤|S|≤105
• SumSum ofof |S||S| overover allall testtest casescases 105≤105

### Sample Input: Raging Infernape solution codechef

1
ababa


### Sample Output: Raging Infernape solution codechef

532396991


### EXPLANATION:

Valid X’s are, X(“a”) = “aba”, X(“b”) = “bab”, X(“ab”) = “abab”, X(“ba”) = “baba”, X(“aba”) = “ababa”. Expected Power is, (3 * 3 + 3 * 2 + 4 * 2 + 4 * 2 + 5 * 2) / 15 = 532396991.