This is the easy version of the problem. The only difference between the two versions is the constraint on .
Given a string of length consisting of lowercase letters only, please calculate the number of 4-tuples satisfying following conditions:

• 
• 
• 
• is lexicographically greater than

Here, represents a substring of which start from the -th character and end at -th character(inclusive).
String is lexicographically less than string , if either is a prefix of (and ), or there exists such , that , and for any . Here denotes the length of the string .
As the answer may be too big, please output the answer module .

The first line contains a single integer  --- the number of test cases.
The first line of each test case contains a single integer  --- the length of the string.
The second line of each test case contains a string  of length  consisting of lowercase letters only.
It is guaranteed that  over all test cases.

For each test case, output a single integer represents the answer module .

2
3
aab
3
aba

2
4