Nasser's Bitwise OR and String - Repovive Starter Round 5 | Repovive

17F. Nasser's Bitwise OR and String

3000 pts2s256 MB

Nasser gives you an array $a$ consisting of integers and a string $s$ consisting of only the characters 'a' and 'b', both having the same length $n$ .

He asks you to count the number of subarrays $[l, r]$ such that:

The number of ones in the bitwise OR of the elements $a[l], a[l+1], \ldots, a[r]$ is equal to the number of 'a' characters in the substring $s[l \ldots r]$ .

A subarray means a continuous segment of the array. For example, in $[1, 2, 3]$ , the subarrays are $[1]$ , $[2]$ , $[3]$ , $[1, 2]$ , $[2, 3]$ , and $[1, 2, 3]$ .

The bitwise OR of several integers is an operation that compares their binary representations bit by bit, and sets each bit to $1$ if any of the numbers has that bit equal to $1$ .

For example: $5 = 101_2$ (binary), $3 = 011_2$ (binary), and $5 \,|\, 3 = 111_2 = 7$ .

Input

Each test contains 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 a single integer $n$ $(1 \le n \le 2 \cdot 10^5)$ - the length of the array and string.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(0 \le a_i < 2^{30})$ - the elements of the array.

The third line of each test case contains a string $s$ of length $n$ , consisting of characters 'a' and 'b' only.

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

Output

For each test case, print a single integer — the number of subarrays $[l, r]$ that satisfy the condition.

Samples

Input

Case 1

3
1 2 3
aba

Case 2

4
4 2 7 1
abba

Explanation

$n=3$ , $a=[1,2,3]$ , $s=$ "aba":

Subarray $[1,1]$ : $\text{OR} = 1 = 001_2$ (ones = $1$ ). The 'a' count in $s[1..1]=$ "a" is $1$ . Since $1=1$ , this is Valid.

Subarray $[2,2]$ : $\text{OR} = 2 = 010_2$ (ones = $1$ ). The 'a' count in $s[2..2]=$ "b" is $0$ . Since $1 \neq 0$ , this is Invalid.

Subarray $[3,3]$ : $\text{OR} = 3 = 011_2$ (ones = $2$ ). The 'a' count in $s[3..3]=$ "a" is $1$ . Since $2 \neq 1$ , this is Invalid.

Subarray $[1,2]$ : $\text{OR} = 1 \mid 2 = 3 = 011_2$ (ones = $2$ ). The 'a' count in $s[1..2]=$ "ab" is $1$ . Since $2 \neq 1$ , this is Invalid.

Subarray $[2,3]$ : $\text{OR} = 2 \mid 3 = 3 = 011_2$ (ones = $2$ ). The 'a' count in $s[2..3]=$ "ba" is $1$ . Since $2 \neq 1$ , this is Invalid.

Subarray $[1,3]$ : $\text{OR} = 1 \mid 2 \mid 3 = 3 = 011_2$ (ones = $2$ ). The 'a' count in $s[1..3]=$ "aba" is $2$ . Since $2=2$ , this is Valid.

Result: The valid subarrays are $[1,1]$ and $[1,3]$ . Answer: $2$