Chef and Abhishek both are fighting for the post of Chairperson to be part of ACE committee and are trying their best. To select only one student their teacher gave them a binary string (string consisting of only 0's and 1's) and asked them to find number of sub-strings present in the given string that satisfy the following condition:
The substring should start with 0 and end with 1 or the substring should start with 1 and end with 0 but not start with 0 and end with 0 and start with 1 and end with 1.
More formally, strings such as 100,0101 are allowed since they start and end with different characters. But strings such as 0110,1101 are not allowed because they start and end with same characters.
Both Chef and Abhishek try their best to solve it but couldn't do it. You being a very good friend of Chef, he asks for your help so that he can solve it and become the Chairperson.

-----Input:-----
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the length of the string.
The second line of each test case contains a binary string of length N.

-----Output:-----
For each test case, print a single line containing one integer ― the number of sub strings satisfying above conditions.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq N \leq 10^9$
Binary string consist's only 0 and 1.

-----Sample Input:-----
1
4

1010

-----Sample Output:-----
4

-----EXPLANATION:-----
All possible substring are : { (1),(0),(1),(0),(10),(01),(10),(101),(010),(1010) }. Out of these only 4 substrings {(10),(01),(10),(1010)} start and end with different characters. Hence the answer 4.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = "from functools import lru_cache\r\nimport sys\r\ntry:\r\n    from cp import input\r\nexcept:\r\n    def input():\r\n        return sys.stdin.readline()\r\ntry:\r\n    import numpy as np\r\nexcept:\r\n    pass\r\nimport math\r\nimport copy\r\nimport random\r\nfrom copy import deepcopy\r\n# def input(): return sys.stdin.readline()\r\ndef itarr(arr): return list(range(len(arr)))\r\ndef mp(): return list(map(int, input().split()))\r\ndef lmp(): return list(map(int, input().strip().split()))\r\ndef inp(): return int(input())\r\n\r\n\r\nMOD = 1000000007\r\n\r\n\r\nsys.setrecursionlimit(100000)\r\nsys.settrace\r\ninf_p = float('inf')\r\ninf_n = float('-inf')\r\n\r\ndsu=[]\r\n\r\ndef find(n):\r\n    if n==dsu[n]:\r\n        return n\r\n    tmp=find(dsu[n])\r\n    dsu[n]=tmp\r\n    return tmp\r\n\r\ndef union(a,b):\r\n    a=find(a)\r\n    b=find(b)\r\n    if a!=b:\r\n        dsu[b]=a\r\n\r\nadj=[]\r\nvis=[]\r\nwt=[]\r\nMAXE=0\r\nMAXO=0\r\nans=0\r\n\r\ndef even_parity(n):\r\n    return (bin(n)[2:].count('1')%2)==0\r\ndef odd_parity(n):\r\n    return not even_parity(n)\r\n\r\ndef dfse(curr_node,p):\r\n    nonlocal MAXE, MAXO,vis,ans\r\n\r\n    for node in adj[curr_node]:\r\n        if vis[node]==0 :\r\n            if even_parity(wt[node-1]):\r\n                dfs(node,num)\r\n        \r\ndef dfso(curr_node,p):\r\n    nonlocal MAXE, MAXO,vis,ans\r\n    \r\n    for node in adj[curr_node]:\r\n        if vis[node]==0 :\r\n            if odd_parity(wt[node-1]):\r\n                dfs(node,num)\r\n\r\ndef main():\r\n    n=inp()\r\n    s=input().strip()\r\n    if len(s)==0:\r\n        s=input().strip\r\n    ones=[0]* (n+1)\r\n    zeros=[0]* (n+1)\r\n    one =0 \r\n    zero=0\r\n    for i in range(len(s)):\r\n        ones[i]=one\r\n        zeros[i]=zero\r\n        if s[i]=='1':\r\n            one+=1\r\n        else:\r\n            zero+=1 \r\n    tot=0\r\n    # print(ones,zeros)\r\n    for i in range(n-1,0,-1):\r\n        if s[i]=='1':\r\n            tot+=zeros[i]\r\n        else:\r\n            tot+=ones[i]\r\n        # print(i)\r\n    print(tot)\r\n\r\n# main()\r\nfor i in range(inp()):\r\n    main()\r\n# cook your dish here\r\n"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: