Description

刘老板在他的家乡拥有一个矿山，他手下的员工每天都在矿山勤勤恳恳地为他挖矿。因为刘老板喜欢数据结构，所以这个万恶的资本家在压榨他的员工们的同时还非常刁钻地要求他的员工们按照二叉搜索树的树形结构来挖矿。

他有n个员工，编号从1到n，他们站成一排，一个一个地站在地面上开始挖矿洞(不用按照编号顺序站）。每个员工只会挖一个洞并且他们只能待在他们挖的那个洞里。站在第一个的员工挖第一个洞，洞里有一条通往地面的通道，然后其他员工穿过通道挖更多的洞和通道。一个洞最多可以有三条通道与之相连，一个在下面，剩下两个在上面，分别位于左上侧和右上侧。当员工到达一个矿洞时，如果他的编号小于洞主人(即挖这个洞的人)的编号的话，他就会进入左上侧的洞（或在左上侧没有洞的情况下挖出一个洞并停留在那里），如果他的编号大于洞主人的话他会进入右上侧的洞（或在右上侧没有洞的情况下挖出一个洞并停留在那里）。因为刘老板经常提出刁钻的要求，所以员工们的能力都被锻炼得很好，他们挖出来的这些洞和通道不会互相交叉。

马上要过春节了，刘老板虽然自己要回家过年，但是他并不打算给他的员工们放假。他准备在回家之前先去看看他的员工们的工作情况顺便大发慈悲的送点年礼来让员工们不要回家继续为他工作。刘老板送年礼有一条规则：编号较小的员工要比编号大的员工更早得到礼物。他从地面开始进入矿山，经过那些矿洞和通道，在送出所有礼物后回到地面。当刘老板到达一个矿洞时，他会记下洞主人编号的奇偶（0代表偶数，1代表奇数），回到地面后他会得到一个01串。为了让题目变得更加麻烦，雷王打算友情提供给刘老板一个漂亮的01子串，刘老板想知道雷王给自己的这个01子串能在他送完礼物之后得到的那个01串里出现几次。

注：由于刘老板记性不好，所以对于同一个人，遇见几次他就会记录几次对方的编号。

Input Format

第一行包含一个整数t，表示有t个测试用例（t<=100）。

对于每个测试用例：

第一行是整数n，表示有n个员工。（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