原码与补码

原码表示法是一种最简单的机器数表示法，其最高位为符号位，符号位为0时表示该数为正，符号位为1时表示该数为负，数值部分与真值相同。特殊地，真值0有两种不同的原码表示形式（举例中设机器的字长为4，下同）：0000和1000；
补码的符号位表示方法与原码相同，其数值部分的表示与数的正负有关，对于正数，数值部分与真值形式相同，对于负数，将真值的数值部分按位取反，且在最低位上加1。特殊地，补码为1000时，对应的真值时-8，没有原码。
现在不同的机器字长下，给出一些整数的原码或补码，求出他们的真值,并用二进制表示。

输入包含多组测试数据，第一行为一个正整数 T ( 1 ≤ T ≤ 1000 )组测试数据。
对于每组测试数据，
第一行包含两个整数 n ( 2≤n≤63 )表示机器的字长和 k ( 0 ≤ k ≤ 1 )。
第二行包含一个字符串 s（长度为 n ，仅包含数字0或1）。当 k=0 时，s 表示原码，当 k=1 时，s 表示补码。

输出 T 行，每行包含一个二进制整数，表示 s 的真值。

3
4 0
0010
4 1
1111 
8 1
10000000

10
-1
-10000000

对于样例1，s表示原码，且为正数，真值与原码相同；对于样例2，字长为4时，-1的补码为1111；对于样例3，s的真值为-128。每个整数的真值表示是唯一的。