ADDITIONAL2

#pragma hdrstop
#pragma argsused

#ifdef _WIN32
#include <tchar.h>
#else
  typedef char _TCHAR;
  #define _tmain main
#endif

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

using namespace std;
int b(int k, int n, int m)
{
	int ans = 1;
	while (n) {
		if (n % 2) {
			ans *= k;
			ans %= m;
		}
		k *= k;
		k %= m;
		n /= 2;
	}
	return ans;
}

void doEverything(int times, int* mas)
{
	if (!times) {
		return;
	}
	int L, m;
	cin >> L >> m;
	char* s1 = new char[201];
	char* s2 = new char[201];
	cin >> s1;
	cin >> s2;
	int l1 = strlen(s1);
	int l2 = strlen(s2);
	int l = L - l1 - l2;
	if (l>0){ mas[times] = 2 * b(26, l, m); }
	else if (!l) { mas[times] =1; }
	else {
		bool ans = true;
		for (int i = l1 + l; i < l1; i++)
		{

			if (s1[i] != s2[i - l1 - l]){
				ans = false;
				break;
			}
		}
		if (ans) { mas[times] = 1; }
	}
	delete[]s1;
	delete[]s2;
	doEverything(times - 1, mas);
}
int _tmain(int argc, _TCHAR* argv[])
{
	int mas[100] = { 0 };
	int times;
	cin >> times;
	doEverything(times, mas);
	for (int i = times ; i > 0; i--)
	{
		cout << mas[i] << endl;
	}
	getch();
	return 0;

}