Description

魔王肖在安排他让爪牙桂抓过来的苦力，那些苦力都在矿山上挖矿，但是魔王肖有一个特别的爱好，他让爪牙桂抓来苦力以一种特别的方式干活。

爪牙桂一共抓来了n个苦力，编号从1到n，他们站成一排，一个一个地站在地面上开始挖矿洞(不用按照编号顺序站）。每个苦力只会挖一个洞并且他们只能待在他们挖的那个洞里。站在第一个的苦力挖第一个洞，洞里有一条通往地面的通道，然后其他苦力穿过通道挖更多的洞和通道。一个洞最多可以有三条通道与之相连，一个在下面，剩下两个在上面，分别位于左上侧和右上侧。当苦力到达一个矿洞时，如果他的编号小于洞主人(即挖这个洞的人)的编号的话，他就会进入左上侧的洞（或在左上侧没有洞的情况下挖出一个洞并停留在那里），如果他的编号大于洞主人的话他会进入右上侧的洞（或在右上侧没有洞的情况下挖出一个洞并停留在那里）。苦力们挖出来的这些洞和通道保证不会互相交叉。不然会魔王肖会不回放过他们的。

一天魔王肖带着爪牙桂来看看矿场的情况，调查一下人口，魔王肖会先从编号小的苦力要先比编号大的苦力先调查。他从地面开始进入矿山，经过矿洞和通道，调查完所有苦力之后回到地面，当魔王肖到达一个矿洞时，他会记下洞主人编号的奇偶（0代表偶数，1代表奇数），回到地面后他会得到一个01串。之后，爪牙肖给魔王肖一个漂亮的01子串，魔王肖想知道爪牙桂给自己的这个01子串能在他调查完之后得到的那个01串里出现几次。魔王肖说：如果有人能够知道结果，可以考虑放过他。

注：由于魔王肖记性不好，所以对于同一个苦力，遇见几次他就会记录几次对方的编号

Input Format

第一行包含一个整数T表示测试用例数（1≤T≤100）。

对于每组测试用例：

第一行是整数n，表示有n个苦力。（1≤n≤30000）。

第二行包含表示苦力编号的n个整数。每个整数是一个编号，第一个整数是站成一排的苦力中第一个苦力的编号。

第三行是爪牙桂提供的01子串。这个子串的长度不大于7000。

Output Format

对于每组测试用例，请输出爪牙桂给的01子串在魔王肖自己的01串里能出现几次。

2
8
5 1 3 2 7 8 4 6
01
10
1 2 3 4 5 6 7 8 9 10
1010

4
8

Source

1816 Online Judge 10.100.0.232