#include <stdio.h>
#include <ctype.h>
#include <string.h>

#define MAX_LENGTH 10000+100000


void debug_print(char *a, int len) {
  int i;
  for (i = 0; i < len; i++)
    putchar(a[i]+'0');
  putchar('\n');
}


/** 
 * In generell the digits in each char get converted to their value,
 * which means, they are no longer 0-terminated strings, so be careful
 * with strlen
 */

/*
 * result = a + reverse(a)  in system with base base 
 *  strings have to be stored in reverse order
 *  len = len(a)
 *  returns rlen(result)
 */
int add_reverse(char *a, char *result, int len, int base) {
  int i, resultLen = len;
  char carry = 0;

  for (i = 0; i < len; i++) {
    result[i] = (a[i] + a[len-1 - i] + carry) % base;
    carry = (a[i] + a[len-1 - i] + carry) / base;
  }
  if (carry > 0) {
    result[resultLen] = 1;
    resultLen++;
    result[resultLen] = 0;
  }
  return resultLen;
}


/*
 * increases a by one
 *
 * returns the new len(a)
 */
int inc(char *a, int len, int base) {

  int i, carry = 1;
  char tmp;

  for (i = 0; i < len; i++) {
    tmp = (a[i] + carry) % base;
    carry = (a[i] +  carry) / base;
    a[i] = tmp;
  }
  if (carry > 0) {
    a[len] = 1;
    len++;
    a[len] = 0;
  }
  return len;

}

/* 
 * reverse string to avoid often appearing strlen calls 
 * also replaces each character with the value which is assigned
 * to the letter, i.e. '0'..'9' = 0..9, 'a'..'z' = 10..36
 *
 * returns the len(a)
 */
int reverse_and_convert(char *a) {
  int l;
  int start = 0, end;
  int tmp;
  char *p = a;


  l = 0;
  while (*p) {
    if (isdigit(*p)) {
      *p = *p - '0';
    } else if (islower(*p)) {
      *p = *p - 'a' + 10;
    }
    p++;
    l++;
  }

  end = l-1;
  while (start < end) {
    tmp = a[start];
    a[start] = a[end];
    a[end] = tmp;
    start++;
    end--;
  }
  return l;
}

/*
 * checks if a is palindrome
 */
int is_palindrom(char *a, int len) {
  int start = 0;

  len--;
  while (start < len) {
    if (a[start] !=  a[len])
      return 0;
    start++;
    len--;
  }
  return 1;
}

/**
 * returns the number of iterations till a is a palindrom, or 
 * -1, in case it isnt terminating in MaxIter iterations
 *
 *  a is changed!
 */
int palindrome_terminate(char *a, int len, int maxIter, int base) {
  int iter;
  char result[MAX_LENGTH];	

  if (is_palindrom(a, len))
    return 0;
  for (iter = 1; iter <= maxIter; iter++) {
    /*printf("iteration %i result:", iter);*/
    len = add_reverse(a, result, len, base);
    /*debug_print(result, len);*/
    memcpy(a, result, len);
    if (is_palindrom(a, len))
      return iter;
  }
  return -1;
}

int main() {

  char end[MAX_LENGTH], current[MAX_LENGTH], tmp[MAX_LENGTH];
  int curlen, endlen;
  int base, maxIterations;
  int numberProblems;
  int numberDivergent, sumKonvergent;
  int iterations;
  int count;
  int I = 1;

  scanf("%i\n", &numberProblems);
  while (numberProblems-- > 0) {
    scanf("%i %i\n", &base, &maxIterations);
    scanf("%s\n %s\n", current, end);
    curlen = reverse_and_convert(current);
    endlen = reverse_and_convert(end);
    sumKonvergent = 0;
    numberDivergent = 0;
    count = 0;
    endlen = inc(end, endlen, base);
    while (memcmp(current, end, endlen)) {
      memcpy(tmp, current, curlen);
      iterations = palindrome_terminate(tmp, curlen, maxIterations, base);
      if (iterations == -1)
        numberDivergent++;
      else
        sumKonvergent += iterations;
      count++;
      curlen = inc(current, curlen, base);
    }

    printf("Scenario %d:\n", I++);
    printf("%i", numberDivergent);
    /*if ((count - numberDivergent) == 0)*/
      /*printf("n.a.\n");*/
    /*else */
      /*printf("%.3f\n", (sumKonvergent/(float)(count-numberDivergent))); */
    printf("\n");
  }
  return 0;
}

