var
  i,j,k,l,o,t,len:longint;
  s,st:string;
  num:array[1..20,1..20] of longint;
  dp:array[1..20,1..20,0..200] of longint;
  function min(x,y:longint):longint;
  begin if x<y then min:=x else min:=y; end;
begin
  assign(input,'puzzle.in'); reset(input);
  assign(output,'puzzle.out'); rewrite(output);
  readln(s);
  readln(t);
  while t>=0 do
    begin
      for i:=1 to 20 do
        for j:=1 to 20 do
          num[i,j]:=9999;
      len:=length(s);
      for i:=1 to len do
        for j:=i to len do
          begin
            st:=copy(s,i,j-i+1);
            while (length(st)>1)and(st[1]='0') do delete(st,1,1);
            if length(st)<4 then val(st,num[i,j]);
          end;
      fillchar(dp,sizeof(dp),$7F div 2);
      for i:=1 to len do
        for j:=i to len do
          begin
            if num[i,j]<=t then
              dp[i,j,num[i,j]]:=0;
            if num[i,j]=0 then
              begin
                for k:=1 to i do
                  dp[k,i,0]:=min(dp[k,i,0],1);
                for k:=j to len do
                  dp[j,k,0]:=min(dp[j,k,0],1);
                for k:=1 to i do
                  for l:=j to len do
                    dp[k,j,0]:=min(dp[k,j,0],2);
              end;
          end;
      for i:=1 to len do
        for j:=1 to len-i+1 do
          for k:=0 to t do
            begin
              for o:=0 to k do
                for l:=j to j+i-2 do
                  dp[j,j+i-1,k]:=min(dp[j,j+i-1,k],dp[j,l,o]+dp[l+1,j+i-1,k-o]+1);
              if k=0 then
                begin
                  for l:=j to j+i-2 do
                    begin
                      dp[j,j+i-1,0]:=min(dp[j,j+i-1,0],dp[j,l,0]+1);
                      dp[j,j+i-1,0]:=min(dp[j,j+i-1,0],dp[l+1,j+i-1,0]+1);
                      for o:=l to j+i-2 do
                        dp[j,j+i-1,0]:=min(dp[j,j+i-1,0],dp[l,o,0]+2);
                    end;
                  continue;
                end;
              for o:=1 to k do
                if k mod o=0 then
                  for l:=j to j+i-2  do
                    dp[j,j+i-1,k]:=min(dp[j,j+i-1,k],dp[j,l,o]+dp[l+1,j+i-1,k div o]+1);
            end;
      if dp[1,len,t]<9999 then writeln(dp[1,len,t]) else writeln(-1);
      readln(s);
      readln(t);
    end;
  close(input); close(output);
end.