#include <iostream.h>
#include <string.h>

void
get_str (char *s)
{
  char c;
  int i = 0;
  
  c = 0;
  
  while ((c = cin.peek()) == ' ' || c == '\n') cin.get();
  
  while (c != ' ' && c != '\n' && i < 20) {
    c = cin.peek();
    if (c != ' ' && c != '\n') {
      cin >> s[i++];
    }
  }
  
  s[i] = '\0';
  
}

int
b2i (char c)
{
  if (c >= '0' && c <= '9') return c - '0';
  if (c >= 'A' && c <= 'Z') return c - 'A' + 10;
  if (c >= 'a' && c <= 'z') return c - 'a' + 36;
  return 0;
}

char
i2b (int i)
{
  if (i >= 0 && i <= 9) return i + '0';
  if (i >= 10 && i <= 35) return i + 'A' - 10;
  if (i >= 36 && i <= 61) return i + 'a' - 36;
  return '0';
};

void
mul_i (char *s, int I, int b)
{
  int i;
  int n = 0;
  
  for (i = 19; i >= 0; i--) {
    n += b2i(s[i]) * I;
    s[i] = i2b(n % b);
    n /= b;
  };
  
}

void
add_i (char *s, int i, int b)
{
  int j;
  int n;
  
  n = i;
  for (j = 19; j >= 0; j--) {
    n += b2i(s[j]);
    s[j] = i2b(n % b);
    n /= b;
  }
}


void
cvt_to_N (char *s2, char *s, int base1, int base2) {
  int i;
  int l;
  l = strlen (s);
  
  for (i = 0; i < l; i++) {
    mul_i (s2, base1, base2);
    add_i (s2, b2i(s[i]), base2);
  };
}

char *
adj_ptr (char *s)
{
  int i = 0;
  
  while (i < 20 && s[i] != 0 && s[i] == '0')
    i++;
  
  return s + i;
}

void
mv_str (char *s)
{
  int i;
  int l = strlen (s);
  
  for (i = 0; i<=l; i++) {
    s[21-i] = s[l-i];
    s[l-i] = '0';
  };
  
}

int
main (int argc, char **argv)
{
  char s1[21], s2[21];
  char *ps1, *ps2;
  
  int b1, b2;
  
  int d_sets;
  int dc;
  
  cin >> d_sets;
  
  for (dc = 1; dc <= d_sets; dc++) {
    for (int i = 0; i < 20; i++) {s1[i] = s2[i] = '0';};
    s1[20]=s2[20] = 0;
    
    get_str (s1);
    mv_str(s1);
    
    cin >> b1 >> b2;	
    
    cvt_to_N (s2, s1, b1, b2);
    
    ps1 = adj_ptr(s1);
    ps2 = adj_ptr(s2);
    
    cout << ps1 << " base " << b1 << " = " << ps2 << " base " << b2 << endl;
    
  }

  return 0;
}