B. Paranoid String

Problem - 1694B - Codeforces

B. Paranoid String

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's call a binary string TT of length mm indexed from 11 to mm paranoid if we can obtain a string of length 11 by performing the following two kinds of operations m−1m−1 times in any order :

• Select any substring of TT that is equal to 01, and then replace it with 1.
• Select any substring of TT that is equal to 10, and then replace it with 0.

  For example, if T=T= 001, we can select the substring [T2T3][T2T3] and perform the first operation. So we obtain T=T= 01.

You are given a binary string SS of length nn indexed from 11 to nn. Find the number of pairs of integers (l,r)(l,r) 1≤l≤r≤n1≤l≤r≤n such that S[l…r]S[l…r] (the substring of SS from ll to rr) is a paranoid string.

Input

The first line contains an integer tt (1≤t≤10001≤t≤1000) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the size of SS.

The second line of each test case contains a binary string SS of nn characters S1S2…SnS1S2…Sn. (Si=Si= 0 or Si=Si= 1 for each 1≤i≤n1≤i≤n)

It is guaranteed that the sum of nn over all test cases doesn't exceed 2⋅1052⋅105.

Output

For each test case, output the number of pairs of integers (l,r)(l,r) 1≤l≤r≤n1≤l≤r≤n such that S[l…r]S[l…r] (the substring of SS from ll to rr) is a paranoid string.

Example

input

Copy

5
1
1
2
01
3
100
4
1001
5
11111

output

Copy

1
3
4
8
5

Note

In the first sample, SS already has length 11 and doesn't need any operations.

In the second sample, all substrings of SS are paranoid. For the entire string, it's enough to perform the first operation.

In the third sample, all substrings of SS are paranoid except [S2S3][S2S3], because we can't perform any operations on it, and [S1S2S3][S1S2S3] (the entire string).

=========================================================================

从后往前考虑，当前若是1,前面是1的话，那么该位置无法向前扩展，否则，一旦前面是0，那么i位置一定能够或者i-1次的缩小为1

例如                    000000001

又例如  0000100010100001   最后一个1可以借助前面的0为其扫清障碍，因为10=0，这样的话可以一路平推到首部

同理  10000000000000000

000010000100111100000000010也是如此，一路平推

最后别忘了加上长度，单个也算

#include <iostream>

typedef long long int ll;
using namespace std;



int main()
{
    int t;

    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;

        string s;

        cin>>s;

        ll ans=0;
        s=" "+s;
        s[0]=s[1];

        for(int i=1;i<=n;i++)
        {
            if(s[i]!=s[i-1])
                ans+=i-1;
        }
        cout<<ans+n<<endl;
    }

    return 0;
}