while 1
  x = gets.split(' ')
  n = x[0].to_i
  m = x[1].to_s
  if(n==0)
    break
  end
  res = 0
  for i in 0..(m.length-1)
    res*=n
    if(m[i]=='0')
      res+=0
    end
    if(m[i]=='1')
      res+=1
    end
    if(m[i]=='2')
      res+=2
    end
    if(m[i]=='3')
      res+=3
    end
    if(m[i]=='4')
      res+=4
    end
    if(m[i]=='5')
      res+=5
    end
    if(m[i]=='6')
      res+=6
    end
    if(m[i]=='7')
      res+=7
    end
    if(m[i]=='8')
      res+=8
    end
    if(m[i]=='9')
      res+=9
    end
    if(m[i]=='A')
      res+=10
    end
    if(m[i]=='B')
      res+=11
    end
    if(m[i]=='C')
      res+=12
    end
    if(m[i]=='D')
      res+=13
    end
    if(m[i]=='E')
      res+=14
    end
    if(m[i]=='F')
      res+=15
    end
    if(m[i]=='G')
      res+=16
    end
    if(m[i]=='H')
      res+=17
    end
    if(m[i]=='I')
      res+=18
    end
    if(m[i]=='J')
      res+=19
    end
    if(m[i]=='K')
      res+=20
    end
    if(m[i]=='L')
      res+=21
    end
    if(m[i]=='M')
      res+=22
    end
    if(m[i]=='N')
      res+=23
    end
    if(m[i]=='O')
      res+=24
    end
    if(m[i]=='P')
      res+=25
    end
    if(m[i]=='Q')
      res+=26
    end
    if(m[i]=='R')
      res+=27
    end
    if(m[i]=='S')
      res+=28
    end
    if(m[i]=='T')
      res+=29
    end
    if(m[i]=='U')
      res+=30
    end
    if(m[i]=='V')
      res+=31
    end
    if(m[i]=='W')
      res+=32
    end
    if(m[i]=='X')
      res+=33
    end
    if(m[i]=='Y')
      res+=34
    end
    if(m[i]=='Z')
      res+=35
    end
  end
  ans = 2**100
  k = n
  for i in 2..n
    if k%i == 0
      tmp = 0
      r = 0
      while k%i==0
        k/=i
        r+=1
    end
      j=i
      while j<=res
        tmp+=res/j
        j*=i
      end
      ans = [ans,tmp/r].min()
    end
  end
  puts ans
end