Do you know how to hash a string? Normally we represent a string in an integer. Then we can transfer from dealing with strings to dealing with integers, which is more convenient. A popular way of hashing a string is:S_hash=∑|S_0,i|*cnt(S_0,i). where S_hash is an integer, which is the hash value. S_0,i is the substring of S from position 0 to position i. cnt(S_0,i) is how many times S_0,i appears in S. Now give you a string S, please calculate the hashed value S_hash.

The first line will be an integer T, which is the number of test case. (1 <= T <= 10)

The first line for each test case will be an integer n, which is the length of string S.

Then there is a line with string S. |S| <= 1000000

S will only contain lower case English letters.

Print an integer for each test case, the hashed value.

Hard problem.