program main;
type
  integer=longint;
const
  maxn=22;
  maxT=220;
  INF=100000;
var
  n,T:integer;
  s:string;
  w:array[1..maxn,1..maxn] of integer;
  f:array[1..maxn,0..maxT] of integer;
  g:array[1..maxn,1..maxn,0..maxT] of integer;

  procedure Fopen;
  begin
    assign(input,'puzzle.in');
    reset(input);
    assign(output,'puzzle.out');
    rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input);
    close(output);
  end;

  procedure Init;
  var
    i,j:integer;
    code:integer;
  begin
    n:=length(s);
    for i:=1 to n do
      for j:=i to n do
        val(copy(s,i,j-i+1),w[i,j],code);
  end;

  procedure Dp;
  var
    i,j,k,l,r,p,q:integer;
  begin
    for k:=1 to n do
      for l:=1 to n-k+1 do
      begin
        r:=l+k-1;
        for p:=0 to T do
        begin
          if w[l,r]=p then g[l,r,p]:=0 else g[l,r,p]:=INF;
          for q:=l to r-1 do
            if (w[q+1,r]>0) and (p mod w[q+1,r]=0) then
              if g[l,q,p div w[q+1,r]]+1<g[l,r,p] then
                g[l,r,p]:=g[l,q,p div w[q+1,r]]+1;
        end;
      end;
    for i:=1 to n do
      for j:=0 to T do
      begin
        f[i,j]:=g[1,i,j];
        for k:=1 to i-1 do
          for p:=0 to j do
            if f[k,p]+g[k+1,i,j-p]+1<f[i,j] then
              f[i,j]:=f[k,p]+g[k+1,i,j-p]+1;
      end;
    if f[n,T]<INF then writeln(f[n,T]) else writeln(-1);
  end;
begin
  Fopen;
  repeat
    readln(s); readln(T);
    if T<0 then break;
    Init;
    Dp;
  until false;
  Fclose;
end.