You and your friend embark on a game set within the framework of a binary tree, governed by a set of rules that stipulate your friends first move, enabling them to place a stone on any node to assert ownership. Following this, its your turn, granting you the liberty to choose any unclaimed node for the placement of your own stone. Assume your friend chooses node x and you choose node y (x = y). Subsequently, continue the game within the binary tree by alternating turns to position stones, following the rule that you are only allowed to place a stone on a node that is either a child or parent of one youve previously marked as yours, as long as the selected location remains unclaimed. When a player is unable to continue placing stones within the binary tree, that player ends the game. If both players end the game, the player who has placed the most stones within the binary tree wins. You are the second player, and you need to determine whether you can choose y in such a way to guarantee a win this game set within the binary tree.

Input The first line of input gives the number of test cases, T (1 T 300). Then T test cases follow each described in the following way: 1. The first line contains a single integer x (1 x 5105 ), indicating the first node your friend selected. 2. The second line contains a single integer n (1 n 5105 and n is odd) indicates the length of array inorder (inorder and level order have the same length). 3. The third line contains n integers in1, in2, ..., inn (1 ini 5 105 ) separated by spaces, which indicate the the inorder traversal of the binary tree. 4. The fourth line contains n integers level1, level2, ..., leveln (1 leveli 5 105 ) separated by spaces, which indicate the the level order traversal of the binary tree. note: inorder and level order consist of unique values. Output For each input, produce one line of output. If you can guarantee that you can win, print 1 otherwise, print 0.

Sample Input

2

3

11

8 4 9 2 10 5 11 1 6 3 7

1 2 3 4 5 6 7 8 9 10 11

1

3

2 1 3

1 2 3

Sample Output

1

0