const maxt=202; maxn=21;
var
 f:array[0..maxn,0..maxt] of longint;
 v:array[0..maxn,0..maxn,0..maxt] of longint;
 s:string; t:longint;
 procedure ready;
 var i,j,l,k,p,kk,x:longint;
 begin
  fillchar(v,sizeof(v),$7f div 2);
  for i:=1 to length(s) do
   begin
    x:=0;
    for j:=i to length(s) do
     begin
      x:=x*10+ord(s[j])-48;
      if x>maxt then x:=maxt;
      v[i,j,x]:=0;
     end;
   end;
  for i:=1 to length(s) do
   for j:=i+1 to length(s) do
    for l:=0 to maxt do
     for k:=i to j-1 do
      for p:=0 to trunc(sqrt(maxt)) do
       begin
        if (p=0) and (l<>0) then continue;
        if p=0 then
         for kk:=0 to maxt do
          if v[i,j,l]>v[i,k,p]+1+v[k+1,j,kk] then
           v[i,j,l]:=v[i,k,p]+1+v[k+1,j,kk];
        if (p<>0) and (l mod p<>0) then continue;
        if p<>0 then
         if v[i,j,l]>v[i,k,p]+1+v[k+1,j,l div p] then
          v[i,j,l]:=v[i,k,p]+1+v[k+1,j,l div p];
       end;
 end;
 procedure dp;
 var i,j,l,k,p:longint;
 begin
  fillchar(f,sizeof(f),$7f div 2);
  p:=f[0,0]; f[0,0]:=0;
  for i:=1 to length(s) do
   for j:=0 to t do
    for k:=0 to i-1 do
     for l:=0 to t do
      begin
       if j<l then break;
       if f[i,j]>f[k,l]+1+v[k+1,i,j-l] then
        f[i,j]:=f[k,l]+1+v[k+1,i,j-l];
      end;
  if f[length(s),t]<>p then writeln(f[length(s),t]-1)
   else writeln(-1);
 end;
begin
 assign(input,'puzzle.in'); reset(input);
 assign(output,'puzzle.out'); rewrite(output);
 readln(s);
 readln(t);
 while t>=0 do
  begin
   ready;
   dp;
   readln(s);
   readln(t);
  end;
 close(input); close(output);
end.