/*
 * @(#) msk98_z.c - Problem 'Z' ("Zeros") solution
 * of the 1st Moscow Students Programming Contest in 1998.
 * (c) 1998 Ivan Maidanski <ivmai@chat.ru> http://ivmai.chat.ru
 * Freeware program source. All rights reserved.
 **
 * Language: C
 * Tested with: Borland C++ v3.1
 * Last modified: 1998-10-17 16:05:00 GMT+04:00
 */

/* Input data file: a.dat */

#include <stdlib.h> /* NULL, strtol(), ltoa() */
#include <string.h> /* strupr() */
#include <stdio.h> /* FILE, EOF, fopen(), fscanf(), printf() */

int primes[]={2,3,5,7,11,13,17,19,21,23,29,31};

int n,m,k;
long v;
char s[256];
int valdegs[sizeof(primes)/sizeof(int)],muldegs[sizeof(primes)/sizeof(int)];

int main()
{
 FILE *f=fopen("a.dat","rt");
 int curn,i;
 if (f==NULL)
  return 1;
 if (fscanf(f,"%*[^0-9]%d",&n)==EOF)
  return 1;
 for (curn=1;curn<=n;curn++)
 {
  if (fscanf(f,"%*[^0-9]%d%*[^0-9]%d",&k,&m)==EOF || k<2 || k>36)
   return 1;
  for (i=0,v=k;i<sizeof(primes)/sizeof(int);i++)
   for (valdegs[i]=muldegs[i]=0;!(v%primes[i]);v/=primes[i],valdegs[i]++);
  while (m--)
  {
   if (fscanf(f,"%*[^0-9A-Za-z]%[0-9A-Za-z]",s)==EOF)
    return 1;
   if (!(v=strtol(s,NULL,k)))
   {
    while (m--)
     if (fscanf(f,"%*[^0-9A-Za-z]%*[0-9A-Za-z]")==EOF)
      return 1;
    break;
   }
   for (i=0;i<sizeof(primes)/sizeof(int);i++)
    if (valdegs[i])
     for (;!(v%primes[i]);v/=primes[i],muldegs[i]++);
  }
  if (v)
  {
   for (i=0,v=-1;i<sizeof(primes)/sizeof(int);i++)
    if (valdegs[i] && (v<0 || v>muldegs[i]/valdegs[i]))
     v=muldegs[i]/valdegs[i];
   if (v<0)
    v=0;
  }
   else v=1;
  printf("----- %d\n"
         "The product has %s trailing zeros.\n",
         curn,strupr(ltoa(v,s,k)));
 }
 return 0;
}