program ikeyb;

type tdata=record
       sum:longint;
       hol:integer;
    end;

var ta,tta:longint;
    skeys,snums:string[255];
    keys,nums:integer;
    i,j,k:integer;
    a:array[1..90] of longint;
    l:longint;
    t:array[1..90,1..90] of tdata;
    d:array[0..90] of integer;
    b,c:tdata;
    gy:array[1..90,1..90] of longint;
    
procedure pre;
  var i,j,k:integer;
  begin
     fillchar(gy,sizeof(gy),0);
     for i:=1 to nums do begin
         for j:=i to nums do begin
	     for k:=i to j do begin
	         inc(gy[i,j],(k-i+1)*a[k]);
		end;
	    end;
       end;
  end;
    
function calc(x,y:integer):longint;
  var l:longint;
      i,j,k,m:integer;
  begin
     l:=0;k:=nums;m:=y;
     for i:=x downto 0 do begin
{         for j:=m+1 to k do inc(l,(j-m)*a[j]);}
	j:=1;
	 inc(l,gy[m+1,k]);
	 k:=m;
	 if i<>0 then m:=t[i,m].hol;
     end;
     calc:=l;
  end;
    
begin
   readln(tta);
   for ta:=1 to tta do begin
       readln(keys,nums);
       readln(skeys);
       readln(snums);l:=0;
       for i:=1 to nums do begin
           readln(a[i]);inc(l,a[i]);
       end;
   pre;
       writeln('Keypad #',ta,':');
       fillchar(t,sizeof(t),0);
       for i:=1 to nums-1 do begin
           t[1,i].sum:=calc(1,i);
       end;
       for i:=1 to keys-2 do begin
           for j:=1 to nums-1 do begin
	       if (t[i,j].sum>0) then begin
	           for k:=j+1 to nums-1 do begin
		       b:=t[i+1,k];
		       t[i+1,k].hol:=j;
		       t[i+1,k].sum:=calc(i+1,k);
		       if (b.sum=0) then begin
		           b:=t[i+1,k];
		       end else begin
		           if b.sum<t[i+1,k].sum then t[i+1,k]:=b;
		       end;
		   end;
	       end;
	   end;
       end;
       fillchar(d,sizeof(d),0);
       l:=t[1,1].sum;j:=nums-1;
       for i:=1 to nums-1 do
           if (t[keys-1,i].sum>0)and(t[keys-1,i].sum<l) then begin l:=t[keys-1,i].sum;j:=i;end;
       i:=keys-1;d[i]:=j;d[i+1]:=nums;
       while (i>0) do begin
           j:=t[i,j].hol;dec(i);
	   d[i]:=j;
       end;d[0]:=0;
       for i:=1 to keys do begin
           write(skeys[i],': ');
	   for j:=d[i-1]+1 to d[i] do write(snums[j]);
	   writeln;
       end;
   end;
end.