program puzzle;
var
  res,min:array[1..20,1..20,0..201] of longint;
  n,i,j,k,l,goal,num1,num2:longint;
  temp:int64;
  s:string;
begin
  assign(input,'puzzle.in'); reset(input);
  assign(output,'puzzle.out'); rewrite(output);
  repeat
    //  Input
    readln(s);
    readln(goal);
    if goal<0 then break;
    n:=length(s);
    //  Prework
    filldword(min,sizeof(min)>>2,maxlongint>>2);
    for i:=1 to n do
      for j:=i to n do begin
        res[i,j][0]:=1;
        val(copy(s,i,j-i+1),res[i,j][1]);
        if res[i,j][1]>200 then begin
          res[i,j][0]:=0; continue;
        end;
        min[i,j][res[i,j][1]]:=0;
      end;
    //  CalMultiply
    for i:=1 to n-1 do
      for j:=1 to n-i do
        for k:=j to i+j-1 do
          for num1:=1 to res[j,k][0] do
            for num2:=1 to res[k+1,i+j][0] do begin
              temp:=int64(res[j,k][num1])*res[k+1,i+j][num2];
              if temp>200 then continue;
              if min[j,i+j][temp]>min[j,k][res[j,k][num1]]+min[k+1,i+j][res[k+1,i+j][num2]]+1 then begin
                if min[j,i+j][temp]>=maxlongint>>2 then begin
                  inc(res[j,i+j][0]);
                  res[j,i+j][res[j,i+j][0]]:=temp;
                end;
                min[j,i+j][temp]:=min[j,k][res[j,k][num1]]+min[k+1,i+j][res[k+1,i+j][num2]]+1;
              end;
            end;
    //  CalPlus
    for i:=1 to n-1 do
      for j:=1 to n-i do
        for k:=j to i+j-1 do
          for num1:=1 to res[j,k][0] do
            for num2:=1 to res[k+1,i+j][0] do begin
              temp:=res[j,k][num1]+res[k+1,i+j][num2];
              if temp>200 then continue;
              if min[j,i+j][temp]>min[j,k][res[j,k][num1]]+min[k+1,i+j][res[k+1,i+j][num2]]+1 then begin
                if min[j,i+j][temp]>=maxlongint>>2 then begin
                  inc(res[j,i+j][0]);
                  res[j,i+j][res[j,i+j][0]]:=temp;
                end;
                min[j,i+j][temp]:=min[j,k][res[j,k][num1]]+min[k+1,i+j][res[k+1,i+j][num2]]+1;
              end;
            end;
    //  Print
    if min[1,n][goal]>=maxlongint>>2 then
      writeln(-1)
    else
      writeln(min[1,n][goal]);
  until false;
  close(input); close(output);
end.