import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main
{
        public static  void main(String[] args)throws IOException
        {
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
               // StringTokenizer datos = new StringTokenizer(br.readLine());

                int T = Integer.parseInt(br.readLine());

                for(int i=0;i<T;i++){
                      StringTokenizer datos = new StringTokenizer(br.readLine());
                      String S=datos.nextToken();
                      BigInteger a = new BigInteger(S,2);
                      BigInteger aux = new BigInteger(new StringBuilder(S).reverse().toString(),2);
                      int hamming = Integer.parseInt(datos.nextToken());
                      Stack<Integer>  pila = new Stack<Integer>();
                      BigInteger bin = BigInteger.ONE.shiftLeft(S.length()-1);
                      int cont=0;
                      BigInteger suma=BigInteger.ZERO;
                      BigInteger res=BigInteger.ZERO;
                      BigInteger numero=BigInteger.ZERO;
                      for(int k=0;k<S.length();k++){
                          numero=bin.shiftRight(k)   ;
                          if((aux.testBit(k))){
                              cont++;
                              suma=suma.add(numero);
                              if(cont==hamming){
                                  k=S.length();
                              }
                          }
                          else{
                              pila.add(S.length()-1-k);
                          }
                      }
                      if(hamming==0){
                          res= a;
                      }
                      else if(cont==hamming)
                          res= a.subtract(suma);
                      else if(cont<hamming)
                      {
                          while(!pila.isEmpty()){
                              res=res.add( new BigInteger("2").pow(pila.pop()));
                              cont++;
                              if(cont==hamming)
                                  pila.removeAllElements();
                          }
                      }
                      StringBuilder sb = new StringBuilder();
                      sb.append("Case #").append(i+1).append(": ").append(String.format(("%"+S.length()+"s"), res.toString(2)).replace(' ','0'));
                      out.println(sb);
                }
                out.flush();
        }
}