#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(func %s, line #%d): " fmt,__func__,__LINE__,##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=1e5+5;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int n,k;
char a[N],b[N];
bool cnt[N];
map<vector<int>,int>mp;
void ljy(){
  scanf("%s%s",a+1,b+1);
  n=strlen(a+1);mp.clear();
  For(i,1,k){
    For(j,1,k) cnt[j]=1;
    vector<int>ans;
    For(j,1,n/k){
      int id=(j-1)*k+i;
      For(p,1,k) if(b[(j-1)*k+p]!=a[id]) cnt[p]=0;
    }For(j,1,k) if(cnt[j]) ans.emplace_back(j);
    if(ans.empty()){puts("0");return;}
    mp[ans]++;
  }ll ans=1;
  for(auto [x,y] within mp){
    if(y!=x.size()){puts("0");return;}
    For(i,1,y) ans*=i;
  }printf("%lld\n",ans);
}
signed LJY(){while(scanf("%d",&k)==1) ljy();}