roy-and-counting-sorted-substrings-1_9753
Roy has a string S of length N. String S is made of lower case English alphabets.  He likes sorted strings. So he wonders how many substrings of S are sorted.  

Given the string S, your task is to count the number of sorted substrings of S.  

A string s is lexicographically sorted if si ≤ si+1  where 1 ≤ i ≤ N-1 (consider 1-based indexing).    

Caution: Use 64-bit integer for count to avoid overflow.  

Input:
First line contains integer T - number of test cases.
First line of each test case contains N - length of string .
Second line contains S  -  the given string.  

Output:
Print the answer for each test case in a new line.  

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 1000000
S consists of only lower case English alphabets [a-z].  

SAMPLE INPUT
4
3
abc
3
bba
4
abac
3
zyxSAMPLE OUTPUT
6
4
6
3Explanation

Test Case #1: 
Substrings of 'abc' are: a, b, c, ab, bc, abc
All these 6 substrings are sorted. Hence the result is 6. 

Test Case #2: 
Substrings of 'bba' are: b, b, a, bb, ba, bba
Out of these 6 substrings, 4 ('b', 'b', 'a' and 'bb') substrings are sorted. So the answer is 4.

Test Case #3: 
Substrings of abac are: a, b, a, c, ab, ba, ac, aba, bac, abac
Out of these 10 substrings, 6 ('a', 'b', 'a', 'c', 'ab' and 'ac') substrings are sorted. Hence the result is 6.

Test Case #4: 
Substrings of zxy are: z, y, x, zy, yx, zyx 
Out of these 6 substrings, only 3 ('z', 'y' and 'x') substrings are sorted. So the answer is 3.
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
t=int(raw_input())
while t:
	t-=1
	n=int(raw_input())
	s=raw_input()
	sort=1
	c=0
	for i in range(1,n):
		if(s[i]>=s[i-1]):
			sort+=1
		else:
			c+= (sort*(sort+1)/2)
			sort=1
	print c+(sort*(sort+1)/2)
4
3
abc
3
bba
4
abac
3
zyxSAMPLE 4
3
abc
3
bba
4
caba
3
zyxSAMPLE 4
3
abc
3
bba
4
aabc
3
zyxSAMPLE 4
3
abc
3
bba
4
caba
3
zzxSAMPLE 4
3
abc
3
bba
4
aabc
3
zxxSAMPLE 4
3
abd
3
bba
4
aabc
2
zyxSAMLPE 4
3
cba
3
aba
4
dbaa
3
zyxSAMPLE 4
3
cba
3
aba
4
bdaa
3
zyxSAMPLE 4
3
cba
3
aba
4
bdaa
1
zyxSAMPLE 4
3
abc
3
aba
4
abac
3
zyxSAMPLE 4
3
cba
3
bba
4
aabc
3
zxxSAMPLE 4
3
cba
3
aba
4
dbaa
4
zyxSAMPLE 4
3
abc
3
bbb
4
aacc
3
zxxSAMPLE 4
3
cbb
3
aba
4
dbaa
4
zyxSAMPLE 4
3
bca
3
aba
4
bdaa
3
zyxSAMPLE 4
2
cba
3
aba
4
bdaa
1
zyxSAMPLE 4
1
cba
3
aba
4
bdaa
1
zyMSAxPLE 4
3
abc
3
aba
4
abac
4
zyxSAMPLE 4
3
abb
3
bca
3
caba
3
zzxSAMPLE 4
1
cba
3
aba
4
dbaa
4
zyxSAMPLE 4
3
abc
3
bbb
4
aacc
1
zxxSAMPLE 4
1
cba
2
aba
4
bdaa
1
zyMSAxPLE 4
1
cba
3
abb
4
dbaa
4
zyxSAMPLE 4
3
abc
3
bbb
4
ccaa
1
zxxSAMPLE 4
3
cbb
3
aba
4
aabd
4
zyxTAMPLE 4
1
cba
2
aba
4
bda`
1
zyMSAxPLE 4
3
abc
3
bba
4
cb`b
8
zyxSAMPLE 4
1
cba
3
abb
4
aabd
4
zyxSAMPLE 4
3
cbb
3
aab
4
aabd
4
zyxTAMPLE 4
3
cba
3
bba
4
cb`b
8
zyxSAMPLE 4
1
cba
3
abb
4
aabd
4
ELPMASxyz 4
3
cbb
3
`ba
4
bd`a
1
zyxSAMPLE 4
3
bbc
3
`ba
4
bd`a
1
zyxSAMPLE 4
3
abc
3
bba
2
cbaa
3
zyxSAMPLE 4
3
abc
3
bba
4
aacc
1
zyxSAMPLE 4
3
abc
3
bba
4
aabc
3
ELPMASxxz 4
3
cba
2
aba
4
bdaa
3
zyxSAMPLE 4
3
abc
3
bba
4
cbaa
7
zyxSAMPLE 4
3
cba
3
bba
4
aabc
4
zxxSAMPLE 4
3
cba
3
bbb
4
aacc
3
zxxSAMPLE 4
3
bca
3
aaa
4
bdaa
3
zyxSAMPLE 4
3
abc
3
bba
4
a`bc
4
zyxSAMPLE 4
2
cba
2
aba
4
bdaa
1
zyMSAxPLE 4
2
cba
2
aba
4
bda`
1
zyMSAxPLE 4
3
cab
3
bba
4
cb`b
8
zyxSAMPLE 4
1
caa
3
bba
4
`acc
3
zxxSALPLE 4
3
bbc
2
`ba
4
bc_a
1
zyxSAMPLE 4
3
abc
2
bba
2
cbaa
3
zyxSAMPLE 4
1
cba
2
aba
4
bdaa
3
zyxSAMPLE 4
3
cbb
3
aba
4
aabd
4
zxxSAMPLE 4
3
bca
3
aaa
4
aadb
3
zyxSAMPLE 4
3
`bc
3
bbb
4
acca
1
zxxSAMPLE 4
3
cbb
3
`ba
4
dbaa
4
ELPMATxyz 4
3
cab
3
bba
4
cb`b
8
zyxSAPMLE 4
1
cab
3
aab
4
aabd
7
zyxTAMPLE 4
3
abd
3
bba
4
cba`
3
zyxSAMLPE 4
3
cbb
3
aba
4
dbaa
4
zxxSAMPLE 4
3
bcb
3
`ba
4
bdaa
2
zyxSAMPLE 4
1
cb`
3
abb
4
aabd
4
zzxSAMPLD 4
3
abc
3
bba
2
abac
3
zyxSAMPLE 4
3
abc
3
bba
4
aabc
6
zyxSAMLPE 4
3
abc
3
cba
4
caba
3
zzxSAMPLE 4
3
abc
2
aba
4
cbaa
3
zyxSAMPLE 4
3
acb
3
bba
4
aabc
3
ELPMASxxz 4
3
dba
3
bba
4
aabc
2
zyxSAMLPE 4
3
abc
3
bca
4
caba
3
ELPMASxzz 4
3
cba
3
aba
4
bdaa
2
zyxSAMPLE 4
3
abc
2
aba
4
abac
3
zyxSAMPLE 4
3
abc
3
aba
4
abac
4
ELPMASxyz 4
3
abc
3
bba
2
cb`b
4
zyxSAMPLE 4
1
cba
3
abb
4
dbaa
4
zyPSAMxLE 4
3
cbb
3
aab
4
aabd
3
zyxTAMPLE 4
3
cba
2
`ba
4
bd`a
1
zyxSAMPLE 4
3
cba
3
bba
2
cb`b
8
zyxSAMPLE 4
2
cb`
3
abb
4
aabd
4
ELPMASxyz 4
3
bbc
3
`ba
4
a_cb
1
zyxSAMPLE 4
3
abc
3
abb
4
aabc
3
ELPMASxxz 4
3
cbc
2
`ba
4
bc_a
1
zyxSAMPLE 4
3
cba
2
bba
2
cbaa
3
zyxSAMPLE 4
3
abd
3
aab
4
aabb
2
zywSAMLPE 4
3
cba
3
aba
4
ada`
1
zyxRAMPLE 4
2
bca
3
aaa
4
aadb
3
zyxSAMPLE 4
3
bbc
3
`ba
4
dbaa
4
ELPMATxyz 4
3
cab
3
bba
4
cb`b
8
zyxSMPALE 4
3
cba
3
aba
4
dbaa
4
zxxSAMPLE 4
3
bca
3
aaa
4
abdb
3
ELPMASxyz 4
3
cba
3
aba
4
dbaa
4
ELPMASxxz 4
2
cb`
3
`bb
4
aabd
4
zzxSAMPLD 4
3
c`b
3
b`b
4
aabd
4
ELPMATxyz 4
3
cbb
3
aaa
4
cbaa
4
ELPMASxxz 4
3
cbb
3
aba
4
a`bc
4
ELPMASxxz 4
3
abc
3
bba
2
abac
3
ELPMASxyz 4
3
abc
2
aba
4
aabc
3
zyxSAMPLE 4
3
bac
3
cba
4
cbaa
4
zyxSAMPLE 4
3
cbb
3
aba
4
dbaa
3
zyxTAMOLE 4
1
cba
3
aba
4
dbaa
4
zyPSAMxLE 4
3
cba
3
bbb
2
cb`b
8
zyxSAMPLE 4
3
abc
3
ba`
4
a`bc
4
zyxSAMPLE 4
2
cba
3
bba
4
aeba
1
{yxSAMPLE 4
1
cb`
3
abb
4
aadb
4
DLPMASxyz 4
3
cba
3
aaa
4
adaa
1
zyxRAMPLE
6
4
6
3
 6
4
5
3
 6
4
10
3
 6
4
5
4
 6
4
10
4
 6
4
10
2
 3
4
5
3
 3
4
6
3
 3
4
6
1
 6
4
6
3
 3
4
10
4
 3
4
5
4
 6
6
10
4
 4
4
5
4
 4
4
6
3
 2
4
6
1
 1
4
6
1
 6
4
6
4
 6
4
4
4
 1
4
5
4
 6
6
10
1
 1
3
6
1
 1
6
5
4
 6
6
6
1
 4
4
10
4
 1
3
5
1
 6
4
5
11
 1
6
10
4
 4
6
10
4
 3
4
5
11
 1
6
10
7
 4
4
6
1
 6
4
6
1
 6
4
2
3
 6
4
10
1
 6
4
10
6
 3
3
6
3
 6
4
5
10
 3
4
10
5
 3
6
10
4
 4
6
6
3
 6
4
7
4
 2
3
6
1
 2
3
5
1
 4
4
5
11
 1
4
10
4
 6
3
6
1
 6
3
2
3
 1
3
6
3
 4
4
10
5
 4
6
7
3
 6
6
7
1
 4
4
5
7
 4
4
5
9
 1
6
10
10
 6
4
4
3
 4
4
5
5
 4
4
6
2
 1
6
10
5
 6
4
3
3
 6
4
10
7
 6
3
5
4
 6
3
5
3
 4
4
10
6
 3
4
10
2
 6
4
5
6
 3
4
6
2
 6
3
6
3
 6
4
6
7
 6
4
2
4
 1
6
5
5
 4
6
10
3
 3
3
6
1
 3
4
2
11
 2
6
10
7
 6
4
5
1
 6
6
10
6
 4
3
6
1
 3
3
2
3
 6
6
10
2
 3
4
5
1
 3
6
7
3
 6
4
5
7
 4
4
5
10
 3
4
5
5
 4
6
7
6
 3
4
5
7
 2
6
10
5
 4
4
10
7
 4
6
5
7
 4
4
7
7
 6
4
3
6
 6
3
10
3
 4
3
5
4
 4
4
5
3
 1
4
5
5
 3
6
2
11
 6
3
7
4
 2
4
5
1
 1
6
7
7
 3
6
6
1
