Erase First or Second Letter

K. Erase First or Second Letter

Problem

You are given a string $s$ of length $n$. Let’s define two operations you can apply on the string:

• remove the first character of the string;
• remove the second character of the string.

Your task is to find the number of distinct non-empty strings that can be generated by applying the given operations on the initial string any number of times (possibly zero), in any order.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains $n$ ($1\le n\le 10^5$) — the length of the string.

The second line of each test case contains the string $s$. It is guaranteed that the string only contains lowercase letters of the English alphabet.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output a single integer: the number of distinct non-empty strings you can get.

Example

Input

5
5
aaaaa
1
z
5
ababa
14
bcdaaaabcdaaaa
20
abcdefghijklmnopqrst

Output

5
1
9
50
210

Note

In the first test case, we can get the following strings: $a$, $aa$, $aaa$, $aaaa$, $aaaaa$.

In the third test case, for example, the word $ba$ can be reached in the following way:

• remove the first character of the current string $ababa$, getting $baba$;
• remove the second character of the current string $baba$, getting $bba$;
• remove the second character of the current string $bba$, getting $ba$.

Code

// #include <iostream>
// #include <algorithm>
// #include <cstring>
// #include <stack>//栈
// #include <deque>//堆/优先队列
// #include <queue>//队列
// #include <map>//映射
// #include <unordered_map>//哈希表
// #include <vector>//容器，存数组的数，表数组的长度
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve()
{
    ll n;
    string s;
    cin>>n>>s;

    map<char,ll> m;
    ll ans=0,sum=0;
    for(ll i=0;i<s.size();i++)
    {
        if(!m[s[i]]) sum++;
        m[s[i]]=1;
        ans+=sum;
    }
    cout<<ans<<endl;
}

int main()
{
    ll t;
    cin>>t;
    while(t--) solve();
    
    return 0;
}