题目描述

As the gardener of the literally Tower of White Jade, Youmu does her jobs perfectly.

But now, Yuyuko the leader of the literally Tower of White Jade finds the normal days are boring, so she wants to do something special, which is collecting the 'spring'. As a leader, of course she will not do it at herself, so she comes to Youmu to let Youmu collect the springs.

As the gardener of the literally Tower of White Jade, Youmu is very willingly to do the job, but now Yuyuko wants to test her before she leaves, just to check if Youmu can do the job perfectly.

Now, Yuyuko wants to do some calculating which is about the bits. She wants to know for a certain positive integer, after some and and or operations, the final results of the certain number.

Youmu, though is a gardener, also a experienced programmer, she solved the problem quickly, so can you solve the problem, too? Which just write a program about bits calculating.

picture: the literally Tower of White Jade

输入格式

The first line of the input contains one positive integers $T (1\\le T\\le1000)$ indicating the number of the test cases.

Then for each test case, first line contains two positive integers $N (1\\le N\\le1000)$ indicating the number of bits operations and $M (0\\le M\\le 10^{18})$ indicating the certain positive integer.

Then for next $N$ lines, each line contains one string indicating the operation, which is as the format below:

And pos [1/0] means do the and operation at position pos with [1/0].

Or pos [1/0] means do the or operation at position pos with [1/0].

It is guaranteed that the $pos(1\\le pos \\le 60)$.

输出格式

For each test case, print one line the final result.

样例

1 
5 0 
And 1 1 
Or 1 1 
Or 2 1 
Or 3 1 
And 2 0

5

1 
5 20210213 
And 60 1 
Or 60 1 
Or 59 1 
And 10 0 
Or 3 1

864691128475344933

1 
5 998244353 
And 60 0 
And 59 0 
And 58 0 
And 57 0 
And 56 0

998244353

提示

It is guaranteed that every positive integer can be expressed by one exact binary number. So the bits calculation is based on the binary number. In the first testcase, the initial number is 0, so we can express it with 000...000, and we do the And 1 1, it becomes 000...000( nothing changed). Then we do Or 1 1, it becomes 000...001 so it becomes 1. As we have done before, we do the Or 2 1, it becomes 000...011, so it becomes 3. Finaly, it becomes 5.