# HackerRank Gridland Provinces Solution

#### ByBrokenprogrammers

Dec 13, 2022

Hello Programmers, In this post, you will Know how to solve HackerRank Gridland Provinces Solution. This problem is a part of the HackerRank Algorithms Series.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.

## HackerRank Gridland Provinces Solution

The Kingdom of Gridland contains P provinces. Each province is defined as a 2 x N grid where each cell in the grid represents a city. Every cell in the grid contains a single lowercase character denoting the first character of the city name corresponding to that cell.

From a city with the coordinates (ij), it is possible to move to any of the following cells in 1 unit of time (provided that the destination cell is within the confines of the grid):

• (i – 1, j)
• (i + 1, j)
• (ij – 1)
• (ij + 1)

A knight wants to visit all the cities in Gridland. He can start his journey in any city and immediately stops his journey after having visited each city at least once. Moreover, he always plans his journey in such a way that the total time required to complete it is minimum.

After completing his tour of each province, the knight forms a string by concatenating the characters of all the cells in his path. How many distinct strings can he form in each province?

Input Format

The first line contains a single integerP, denoting the number of provinces. The 3 x P subsequent lines describe each province over the following three lines:
The first line contains an integer, N, denoting the number of columns in the province.
Each of the next two lines contains a string, S, of length N denoting the characters for the first and second row of the province.

Constraints

• 1 <= P <= 15
• 1 <= N <= 600
• Si ∈ {a – z}

Output Format

For each province, print the number of distinct strings the knight can form on a new line.

Sample Input

3
1
a
a
3
dab
abd
5
ababa
babab

Sample Output

1
8
2

Explanation

Province 0:

The knight can only form one string (`aa`), so we print 1 on a new line.

Province 1:

The knight can form eight different strings (`abdbad``adabdb``badabd``bdbada``dababd``dabdba``dbabad`, and `dbadab`), so we print 8 on a new line.

Province 2:

The knight can form two different strings (`ababababab` and `bababababa`), so we print 2 on a new line.

## HackerRank Gridland Provinces Solution

### Gridland Provinces Solution in C

```#include <stdio.h>
#include <stdlib.h>
#define MOD1 1000000007
#define MOD2 1000000009
#define HASH_SIZE 123455
typedef struct _node{
int x;
int y;
struct _node *next;
} node;
void solve(int i,int j);
void insert(int x,int y);
void freehash();
long long modInverse(long long a,long long mod);
char a[2][601];
int hash_count,N;
long long tr1[1200],tl1[1200],br1[1200],bl1[1200],dr1[1200],dl1[1200],ur1[1200],ul1[1200],mod1[1201],inmod1[1201];
long long tr2[1200],tl2[1200],br2[1200],bl2[1200],dr2[1200],dl2[1200],ur2[1200],ul2[1200],mod2[1201],inmod2[1201];
node *hash[HASH_SIZE]={0};
int main(){
int T,i,j;
long long t1,t2;
scanf("%d",&T);
while(T--){
hash_count=0;
scanf("%d%s%s",&N,&a[0][0],&a[1][0]);
for(i=0,t1=t2=1;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2)
if(i){
tl1[i]=((a[0][i]-'a')*t1+tl1[i-1])%MOD1;
bl1[i]=((a[1][i]-'a')*t1+bl1[i-1])%MOD1;
tl2[i]=((a[0][i]-'a')*t2+tl2[i-1])%MOD2;
bl2[i]=((a[1][i]-'a')*t2+bl2[i-1])%MOD2;
}
else{
tl1[i]=a[0][i]-'a';
bl1[i]=a[1][i]-'a';
tl2[i]=a[0][i]-'a';
bl2[i]=a[1][i]-'a';
}
for(i=N-1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2){
tl1[2*N-i-1]=((a[1][i]-'a')*t1+tl1[2*N-i-2])%MOD1;
bl1[2*N-i-1]=((a[0][i]-'a')*t1+bl1[2*N-i-2])%MOD1;
tl2[2*N-i-1]=((a[1][i]-'a')*t2+tl2[2*N-i-2])%MOD2;
bl2[2*N-i-1]=((a[0][i]-'a')*t2+bl2[2*N-i-2])%MOD2;
}
for(i=N-1,t1=t2=1;i>=0;i--,t1=t1*26%MOD1,t2=t2*26%MOD2)
if(i!=N-1){
tr1[N-i-1]=((a[0][i]-'a')*t1+tr1[N-i-2])%MOD1;
br1[N-i-1]=((a[1][i]-'a')*t1+br1[N-i-2])%MOD1;
tr2[N-i-1]=((a[0][i]-'a')*t2+tr2[N-i-2])%MOD2;
br2[N-i-1]=((a[1][i]-'a')*t2+br2[N-i-2])%MOD2;
}
else{
tr1[N-i-1]=a[0][i]-'a';
br1[N-i-1]=a[1][i]-'a';
tr2[N-i-1]=a[0][i]-'a';
br2[N-i-1]=a[1][i]-'a';
}
for(i=0;i<N;i++,t1=t1*26%MOD1,t2=t2*26%MOD2){
tr1[i+N]=((a[1][i]-'a')*t1+tr1[i+N-1])%MOD1;
br1[i+N]=((a[0][i]-'a')*t1+br1[i+N-1])%MOD1;
tr2[i+N]=((a[1][i]-'a')*t2+tr2[i+N-1])%MOD2;
br2[i+N]=((a[0][i]-'a')*t2+br2[i+N-1])%MOD2;
}
for(i=0,t1=t2=1;i<N;i++){
if(i%2){
ul1[2*i]=((a[0][i]-'a')*t1+ul1[2*i-1])%MOD1;
dl1[2*i]=((a[1][i]-'a')*t1+dl1[2*i-1])%MOD1;
ul2[2*i]=((a[0][i]-'a')*t2+ul2[2*i-1])%MOD2;
dl2[2*i]=((a[1][i]-'a')*t2+dl2[2*i-1])%MOD2;
}
else
if(!i){
ul1[2*i]=a[1][i]-'a';
dl1[2*i]=a[0][i]-'a';
ul2[2*i]=a[1][i]-'a';
dl2[2*i]=a[0][i]-'a';
}
else{
ul1[2*i]=((a[1][i]-'a')*t1+ul1[2*i-1])%MOD1;
dl1[2*i]=((a[0][i]-'a')*t1+dl1[2*i-1])%MOD1;
ul2[2*i]=((a[1][i]-'a')*t2+ul2[2*i-1])%MOD2;
dl2[2*i]=((a[0][i]-'a')*t2+dl2[2*i-1])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
if(i%2){
ul1[2*i+1]=((a[1][i]-'a')*t1+ul1[2*i])%MOD1;
dl1[2*i+1]=((a[0][i]-'a')*t1+dl1[2*i])%MOD1;
ul2[2*i+1]=((a[1][i]-'a')*t2+ul2[2*i])%MOD2;
dl2[2*i+1]=((a[0][i]-'a')*t2+dl2[2*i])%MOD2;
}
else{
ul1[2*i+1]=((a[0][i]-'a')*t1+ul1[2*i])%MOD1;
dl1[2*i+1]=((a[1][i]-'a')*t1+dl1[2*i])%MOD1;
ul2[2*i+1]=((a[0][i]-'a')*t2+ul2[2*i])%MOD2;
dl2[2*i+1]=((a[1][i]-'a')*t2+dl2[2*i])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
for(i=N-1,t1=t2=1;i>=0;i--)
if(i==N-1){
ur1[2*(N-1-i)]=a[1][i]-'a';
dr1[2*(N-1-i)]=a[0][i]-'a';
ur2[2*(N-1-i)]=a[1][i]-'a';
dr2[2*(N-1-i)]=a[0][i]-'a';
t1=t1*26%MOD1;
t2=t2*26%MOD2;
ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
else{
if((N-i)%2==0){
ur1[2*(N-1-i)]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
dr1[2*(N-1-i)]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
ur2[2*(N-1-i)]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
dr2[2*(N-1-i)]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
}
else{
ur1[2*(N-1-i)]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)-1])%MOD1;
dr1[2*(N-1-i)]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)-1])%MOD1;
ur2[2*(N-1-i)]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)-1])%MOD2;
dr2[2*(N-1-i)]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)-1])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
if((N-i)%2==0){
ur1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
}
else{
ur1[2*(N-1-i)+1]=((a[0][i]-'a')*t1+ur1[2*(N-1-i)])%MOD1;
dr1[2*(N-1-i)+1]=((a[1][i]-'a')*t1+dr1[2*(N-1-i)])%MOD1;
ur2[2*(N-1-i)+1]=((a[0][i]-'a')*t2+ur2[2*(N-1-i)])%MOD2;
dr2[2*(N-1-i)+1]=((a[1][i]-'a')*t2+dr2[2*(N-1-i)])%MOD2;
}
t1=t1*26%MOD1;
t2=t2*26%MOD2;
}
for(i=0;i<=2*N;i++)
if(i){
mod1[i]=mod1[i-1]*26%MOD1;
inmod1[i]=modInverse(mod1[i],MOD1);
mod2[i]=mod2[i-1]*26%MOD2;
inmod2[i]=modInverse(mod2[i],MOD2);
}
else
mod1[i]=inmod1[i]=mod2[i]=inmod2[i]=1;
for(i=0;i<=N;i++)
for(j=i;j<=N;j++)
solve(i,j);
printf("%d\n",hash_count);
freehash();
}
return 0;
}
void solve(int i,int j){
long long t1,t2,t3,t4,t5,t6,t7,t8,t9;
long long tt1,tt2,tt3,tt4,tt5,tt6,tt7,tt8,tt9;
t1=tr1[N+i-1];
t2=br1[N+i-1];
if(i!=N){
t1=(t1-tr1[N-i-1]+MOD1)%MOD1;
t2=(t2-br1[N-i-1]+MOD1)%MOD1;
}
t1=t1*inmod1[N-i]%MOD1;
t2=t2*inmod1[N-i]%MOD1;
t3=tl1[2*N-j-1];
t4=bl1[2*N-j-1];
if(j){
t3=(t3-tl1[j-1]+MOD1)%MOD1;
t4=(t4-bl1[j-1]+MOD1)%MOD1;
}
t3=t3*inmod1[j]%MOD1;
t4=t4*inmod1[j]%MOD1;
if(!j)
t5=t6=0;
else{
t5=ul1[2*j-1];
t6=dl1[2*j-1];
if(i){
t5=(t5-ul1[2*i-1]+MOD1)%MOD1;
t6=(t6-dl1[2*i-1]+MOD1)%MOD1;
}
}
if(i==N)
t7=t8=0;
else{
t7=ur1[2*(N-i)-1];
t8=dr1[2*(N-i)-1];
if(j!=N){
t7=(t7-ur1[2*(N-j)-1]+MOD1)%MOD1;
t8=(t8-dr1[2*(N-j)-1]+MOD1)%MOD1;
}
}
tt1=tr2[N+i-1];
tt2=br2[N+i-1];
if(i!=N){
tt1=(tt1-tr2[N-i-1]+MOD2)%MOD2;
tt2=(tt2-br2[N-i-1]+MOD2)%MOD2;
}
tt1=tt1*inmod2[N-i]%MOD2;
tt2=tt2*inmod2[N-i]%MOD2;
tt3=tl2[2*N-j-1];
tt4=bl2[2*N-j-1];
if(j){
tt3=(tt3-tl2[j-1]+MOD2)%MOD2;
tt4=(tt4-bl2[j-1]+MOD2)%MOD2;
}
tt3=tt3*inmod2[j]%MOD2;
tt4=tt4*inmod2[j]%MOD2;
if(!j)
tt5=tt6=0;
else{
tt5=ul2[2*j-1];
tt6=dl2[2*j-1];
if(i){
tt5=(tt5-ul2[2*i-1]+MOD2)%MOD2;
tt6=(tt6-dl2[2*i-1]+MOD2)%MOD2;
}
}
if(i==N)
tt7=tt8=0;
else{
tt7=ur2[2*(N-i)-1];
tt8=dr2[2*(N-i)-1];
if(j!=N){
tt7=(tt7-ur2[2*(N-j)-1]+MOD2)%MOD2;
tt8=(tt8-dr2[2*(N-j)-1]+MOD2)%MOD2;
}
}
t9=t1;
if(i%2)
t9+=t6;
else
t9+=t5;
if((j-i)%2)
t9+=t3*mod1[j*2]%MOD1;
else
t9+=t4*mod1[j*2]%MOD1;
t9%=MOD1;
tt9=tt1;
if(i%2)
tt9+=tt6;
else
tt9+=tt5;
if((j-i)%2)
tt9+=tt3*mod2[j*2]%MOD2;
else
tt9+=tt4*mod2[j*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t2;
if(i%2)
t9+=t5;
else
t9+=t6;
if((j-i)%2)
t9+=t4*mod1[j*2]%MOD1;
else
t9+=t3*mod1[j*2]%MOD1;
t9%=MOD1;
tt9=tt2;
if(i%2)
tt9+=tt5;
else
tt9+=tt6;
if((j-i)%2)
tt9+=tt4*mod2[j*2]%MOD2;
else
tt9+=tt3*mod2[j*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t3;
if((N-j)%2)
t9+=t8;
else
t9+=t7;
if((j-i)%2)
t9+=t1*mod1[(N-i)*2]%MOD1;
else
t9+=t2*mod1[(N-i)*2]%MOD1;
t9%=MOD1;
tt9=tt3;
if((N-j)%2)
tt9+=tt8;
else
tt9+=tt7;
if((j-i)%2)
tt9+=tt1*mod2[(N-i)*2]%MOD2;
else
tt9+=tt2*mod2[(N-i)*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
t9=t4;
if((N-j)%2)
t9+=t7;
else
t9+=t8;
if((j-i)%2)
t9+=t2*mod1[(N-i)*2]%MOD1;
else
t9+=t1*mod1[(N-i)*2]%MOD1;
t9%=MOD1;
tt9=tt4;
if((N-j)%2)
tt9+=tt7;
else
tt9+=tt8;
if((j-i)%2)
tt9+=tt2*mod2[(N-i)*2]%MOD2;
else
tt9+=tt1*mod2[(N-i)*2]%MOD2;
tt9%=MOD2;
insert(t9,tt9);
return;
}
void insert(int x,int y){
int bucket=(x+y)%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->x==x && t->y==y)
return;
t=t->next;
}
t=(node*)malloc(sizeof(node));
t->x=x;
t->y=y;
t->next=hash[bucket];
hash[bucket]=t;
hash_count++;
return;
}
void freehash(){
int i;
node *t,*p;
for(i=0;i<HASH_SIZE;i++){
t=hash[i];
while(t){
p=t->next;
free(t);
t=p;
}
hash[i]=NULL;
}
return;
}
long long modInverse(long long a,long long mod){
long long b0 = mod, t, q;
long long x0 = 0, x1 = 1;
while (a > 1) {
q = a / mod;
t = mod; mod = a % mod; a = t;
t = x0; x0 = x1 - q * x0; x1 = t;
}
if (x1 < 0) x1 += b0;
return x1;
}```

### Gridland Provinces Solution in Cpp

```#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }
unsigned a = 123456789, b = 987654321;
#ifdef __GNUC__
asm(
"rdtsc;\n\t"
: "=d" (a), "=a" (b)
);
#else
__asm {
rdtsc;
mov a, edx;
mov b, eax;
};
#endif
return (unsigned long long)a << 32 | b;
}
unsigned xor128() {
static unsigned x = 123456789, y = 362436069,
unsigned t = x ^ (x << 11);
x = y; y = z; z = w;
return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
struct PolynomialHash {
static const int NumMods = 2;
static const unsigned Mods[NumMods];
typedef unsigned long long ull;
struct Hash {
unsigned hs[NumMods];
Hash() { for(int k = 0; k < NumMods; ++ k) hs[k] = 0; }
bool operator==(const Hash &that) const {
bool res = true;
for(int k = 0; k < NumMods; ++ k)
res &= hs[k] == that.hs[k];
return res;
}
bool operator<(const Hash &that) const {
for(int k = 0; k < NumMods; ++ k)
if(hs[k] != that.hs[k])
return hs[k] < that.hs[k];
return false;
}
//string debugstr;
};
static unsigned seeds[NumMods];
static std::vector<Hash> powh;
static void initSeeds() {
for(int k = 0; k < NumMods; ++ k) {
unsigned x;
do x = xor128(); while(x == 0 || x >= Mods[k]);
seeds[k] = x;
}
}
static void precomputePowerTable(int newSize) {
if((int)powh.size() >= newSize) return;
if(seeds[0] == 0) initSeeds();
int oldSize = powh.size();
powh.resize(newSize);
if(oldSize == 0)
for(int k = 0; k < NumMods; ++ k) powh[0].hs[k] = 1;
for(int i = std::max(1, oldSize); i < newSize; i ++) for(int k = 0; k < NumMods; ++ k)
powh[i].hs[k] = (ull)powh[i - 1].hs[k] * seeds[k] % Mods[k];
}
};
const unsigned PolynomialHash::Mods[PolynomialHash::NumMods] = { 2147483647U, 2147483629U };
unsigned PolynomialHash::seeds[PolynomialHash::NumMods];
std::vector<PolynomialHash::Hash> PolynomialHash::powh;
struct SubstringHash : PolynomialHash {
std::vector<Hash> preh;
string debugS;
template<typename V>
void init(const V &v, int n) {
debugS = v;
precomputePowerTable(n + 1);
preh.resize(n + 1);
preh[0] = Hash();
for(int i = 0; i < n; i ++) for(int k = 0; k < NumMods; ++ k)
preh[i + 1].hs[k] = ((ull)preh[i].hs[k] * seeds[k] % Mods[k] + v[i]) % Mods[k];
}
Hash hash(int j) const {
return preh[j];
}
Hash hash(int i, int j) const {
if(i == 0) return hash(j);
Hash res;
for(int k = 0; k < NumMods; ++ k) {
unsigned x = preh[j].hs[k] + Mods[k] - (unsigned)((ull)preh[i].hs[k] * powh[j - i].hs[k] % Mods[k]);
res.hs[k] = x >= Mods[k] ? x - Mods[k] : x;
}
//res.debugstr = debugS.substr(i, j - i);
return res;
}
Hash append(const Hash &h, const Hash &g, int glen) const {
Hash res;
for(int k = 0; k < NumMods; ++ k) {
unsigned x = (unsigned)((ull)h.hs[k] * powh[glen].hs[k] % Mods[k]) + g.hs[k];
res.hs[k] = x >= Mods[k] ? x - Mods[k] : x;
}
//res.debugstr = h.debugstr + g.debugstr;
//assert(glen == g.debugstr.size());
return res;
}
};
int main() {
PolynomialHash::initSeeds();
int T;
scanf("%d", &T);
for(int ii = 0; ii < T; ++ ii) {
int N;
scanf("%d", &N);
vector<string> S(2);
cin >> S[0] >> S[1];
SubstringHash app;
string tmp(N * 2, '.');
app.init(tmp, N * 2);
vector<SubstringHash::Hash> hashes;
rep(my, 2) {
rep(mx, 2) {
string zigzag[2];
rep(i, N) {
rep(j, 2) {
rep(p, 2)
zigzag[p] += S[(j + i + p) % 2][i];
}
}
SubstringHash zigzagh[2];
rep(p, 2)
zigzagh[p].init(zigzag[p], N * 2);
SubstringHash sh[2], revh[2];
rep(i, 2) {
sh[i].init(S[i], N);
reverse(S[i].begin(), S[i].end());
revh[i].init(S[i], N);
reverse(S[i].begin(), S[i].end());
}
rep(i, N) rer(j, i + 1, N) {
SubstringHash::Hash h;
h = app.append(h, revh[0].hash(N - i - 1, N), i + 1);
h = app.append(h, sh[1].hash(0, i + 1), i + 1);
h = app.append(h, zigzagh[i % 2].hash((i + 1) * 2, j * 2), (j - i - 1) * 2);
int p = (j - i) % 2;
h = app.append(h, sh[p].hash(j, N), N - j);
h = app.append(h, revh[1-p].hash(0, N - j), N - j);
hashes.push_back(h);
}
rep(k, 2)
reverse(S[k].begin(), S[k].end());
}
S[0].swap(S[1]);
}
sort(hashes.begin(), hashes.end());
hashes.erase(unique(hashes.begin(), hashes.end()), hashes.end());
int ans = (int)hashes.size();
printf("%d\n", ans);
}
return 0;
}```

### Gridland Provinces Solution in Java

```import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Random;
import java.util.Set;
public class E4 {
InputStream is;
PrintWriter out;
//    String INPUT = "1 6 abcdef ijklmn";
String INPUT = "";
//    String INPUT = "1 3 abc def";
//    String INPUT = "";

//    String INPUT = "";
void solve()
{
long B1 = BigInteger.probablePrime(29, new Random()).longValue();
long B2 = BigInteger.probablePrime(29, new Random()).longValue();
long M1 = BigInteger.probablePrime(30, new Random()).longValue();
long M2 = BigInteger.probablePrime(30, new Random()).longValue();
long[] ps1 = new long[2000];
long[] ps2 = new long[2000];
ps1[0] = 1;
ps2[0] = 1;
for(int i = 1;i < 2000;i++){
ps1[i] = ps1[i-1] * B1 % M1;
ps2[i] = ps2[i-1] * B2 % M2;
}

for(int T = ni();T > 0;T--){
int m = ni();
char[][] map = nm(2, m);
Set<Long> set = new HashSet<>();
long[][] hs = new long[2][m];
long[][] rhs = new long[2][m];
long[][] hs2 = new long[2][m];
long[][] rhs2 = new long[2][m];
for(int sr = 0;sr < 2;sr++){
for(int l = 1;l < m;l++){
int p = 0;
int r = sr;
long t1 = 0, rt1 = 0;
long t2 = 0, rt2 = 0;
for(int u = l-1;u >= 0;u--){
t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
p++;
}
r ^= 1;
for(int u = 0;u < l;u++){
t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
p++;
}
hs[sr][l] = t1<<32|t2;
rhs[sr][l] = rt1<<32|rt2;
}
}
for(int sr = 0;sr < 2;sr++){
for(int h = m-2;h >= 0;h--){
int p = 0;
int r = sr;
long t1 = 0, rt1 = 0;
long t2 = 0, rt2 = 0;
for(int u = h+1;u < m;u++){
t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
p++;
}
r ^= 1;
for(int u = m-1;u > h;u--){
t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
p++;
}
hs2[sr][h] = t1<<32|t2;
rhs2[sr][h] = rt1<<32|rt2;
}
}
for(int sr = 0;sr < 2;sr++){
int p = 0;
int r = sr;
long t1 = 0, rt1 = 0;
long t2 = 0, rt2 = 0;
for(int u = m-1;u >= 0;u--){
t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
p++;
}
r^=1;
for(int u = 0;u <= m-1;u++){
t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
p++;
}
assert p == 2*m;
}
for(int sr = 0;sr < 2;sr++){
int p = 0;
int r = sr;
long t1 = 0, rt1 = 0;
long t2 = 0, rt2 = 0;
for(int u = 0;u < m;u++){
t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
p++;
}
r^=1;
for(int u = m-1;u >= 0;u--){
t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
p++;
}
assert p == 2*m;
}

//            for(int b = 0;b < m;b++){
//                for(int sr = 0;sr < 2;sr++){
//                    int p = 0;
//                    int r = sr;
//                    long t1 = 0, rt1 = 0;
//                    long t2 = 0, rt2 = 0;
//                    for(int u = b;u < m;u++){
//                        t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
//                        t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
//                        p++;
//                    }
//                    r^=1;
//                    for(int u = m-1;u >= 0;u--){
//                        t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
//                        t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
//                        p++;
//                    }
//                    r ^= 1;
//                    for(int u = 0;u < b;u++){
//                        t1 = (t1 * B1 + map[r][u]) % M1; rt1 = (rt1 + map[r][u] * ps1[p]) % M1;
//                        t2 = (t2 * B2 + map[r][u]) % M2; rt2 = (rt2 + map[r][u] * ps2[p]) % M2;
//                        p++;
//                    }
//                    assert p == 2*m;
//                }
//            }
for(int sr = 0;sr < 2;sr++){
for(int l = 0;l < m;l++){
long t1 = hs[sr][l]>>>32, rt1 = rhs[sr][l]>>>32;
long t2 = (int)hs[sr][l], rt2 = (int)rhs[sr][l];
int r = sr^1;
if(l-1 >= 0){
long xt1 = (t1 * ps1[2*m-(2*l)] + (rhs2[r^1][l-1]>>>32)) % M1;
long xt2 = (t2 * ps2[2*m-(2*l)] + ((int)rhs2[r^1][l-1])) % M2;
long xrt1 = (rt1 + (hs2[r^1][l-1]>>>32) * ps1[2*l]) % M1;
long xrt2 = (rt2 + ((int)(hs2[r^1][l-1])) * ps2[2*l]) % M2;
}
for(int h = l;h < m;h++){
t1 = (t1 * B1 + map[r][h]) % M1; rt1 = (rt1 + map[r][h] * ps1[2*h]) % M1;
t2 = (t2 * B2 + map[r][h]) % M2; rt2 = (rt2 + map[r][h] * ps2[2*h]) % M2;
r ^= 1;
t1 = (t1 * B1 + map[r][h]) % M1; rt1 = (rt1 + map[r][h] * ps1[2*h+1]) % M1;
t2 = (t2 * B2 + map[r][h]) % M2; rt2 = (rt2 + map[r][h] * ps2[2*h+1]) % M2;

long xt1 = (t1 * ps1[2*m-(2*h+2)] + (rhs2[r^1][h]>>>32)) % M1;
long xt2 = (t2 * ps2[2*m-(2*h+2)] + ((int)rhs2[r^1][h])) % M2;
long xrt1 = (rt1 + (hs2[r^1][h]>>>32) * ps1[2*h+2]) % M1;
long xrt2 = (rt2 + ((int)(hs2[r^1][h])) * ps2[2*h+2]) % M2;
//                        tr(sr, l, h, xt, xrt);
}
}
}
//            for(String line : new TreeSet<>(set)){
//                tr(line);
//            }
out.println(set.size());
}
}

void run() throws Exception
{
//        int n = 600, m = 99999;
//        Random gen = new Random();
//        StringBuilder sb = new StringBuilder();
//        sb.append(1 + " ");
//        sb.append(n + " ");
//        for (int i = 0; i < n; i++) {
//            sb.append((char)('a'+gen.nextInt(26)));
//        }
//        sb.append("\n");
//        for (int i = 0; i < n; i++) {
//            sb.append((char)('a'+gen.nextInt(26)));
//        }
//        INPUT = sb.toString();

is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);

long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}

public static void main(String[] args) throws Exception { new E4().run(); }

private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;

{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}

private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }

private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
}
return sb.toString();
}

private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}

private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}

private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}```

### Gridland Provinces Solution in Python

```# Enter your code here. Read input from STDIN. Print output to STDOUT
right = lambda x, y: (x, y + 1)
up = lambda x, y: (x - 1, y)
down = lambda x, y: (x + 1, y)
def Work(a, N):
ans = set([])
def Found(s):
#print "".join(s)

s = list(a[0] + a[1])

def S1():
for p in xrange(N):
for q in xrange(p, N):
parts = []
if p % 2 == 0:
parts.append(a[1][:p][::-1])
parts.append(a[0][:p])
else:
parts.append(a[0][:p][::-1])
parts.append(a[1][:p])
for i in xrange(p, q + 1):
if i % 2 == 0:
parts.append(a[0][i] + a[1][i])
else:
parts.append(a[1][i] + a[0][i])
if q % 2 == 0:
parts.append(a[1][q+1:])
parts.append(a[0][q+1:][::-1])
else:
parts.append(a[0][q+1:])
parts.append(a[1][q+1:][::-1])
Found(parts)
def S2():
s = list(a[0] + a[1][::-1])
for i in xrange(N * 2):
Found(s[i:] + s[:i])
S1()
S2()
a[0], a[1] = a[1], a[0]
S1()
S2()
return len(ans)

for __ in xrange(int(raw_input())):
N = int(raw_input())
a = [raw_input().strip() for i in xrange(2)]
print Work(a, N)```

### Gridland Provinces Solution using JavaScript

```'use strict';
const fs = require('fs');
const _ = require('underscore');
process.stdin.resume();
process.stdin.setEncoding('ascii');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
return inputString[currentLine++];
}
var res = new Set();
function arr2(x, y) {
var a1 = _.range(x).map(() => {
return _.range(y).map((i2) => {
return BigInt(i2);
})
})
return a1
}
function arr(x) {
return _.range(x).map((i) => {
return BigInt(i);
})
}
function* range(start, end) {
for (let i = start; i <= end; i++) {
yield i;
}
}
function shuffle(obj1, obj2) {
var index = obj1.length;
var rnd, tmp1, tmp2;
while (index) {
rnd = Math.floor(Math.random() * index);
index -= 1;
tmp1 = obj1[index];
tmp2 = obj2[index];
obj1[index] = obj1[rnd];
obj2[index] = obj2[rnd];
obj1[rnd] = tmp1;
obj2[rnd] = tmp2;
}
}
var M = BigInt(1202953049705846707);
var u = BigInt(7627744968637);
var u2 = u * u % M
var P = arr(608),
V = arr(128),
L = arr2(2, 608),
R = arr2(2, 608),
X = arr2(2, 608);
function hh(n, a) {
L[0][0] = L[0][1] = R[0][1] = R[0][0] = 0n
let p = u;
for (let i = 1; i <= n; ++i, p = p * u2 % M)
for (let j of range(0, 1)) {
L[j][i] = (BigInt(L[j][i - 1]) * u + BigInt(V[a[j ^ 1][i - 1].charCodeAt(0)]) + BigInt(V[a[j][i - 1].charCodeAt(0)]) * p) % M;
R[j][i] = (BigInt(R[j][i - 1]) * u + BigInt(V[a[j ^ 1][n - i].charCodeAt(0)]) + BigInt(V[a[j][n - i].charCodeAt(0)]) * p) % M;
};
for (let j of range(0, 1)) {
for (let i = 1; i < n; ++i) {
X[j][i] = (BigInt(V[a[j][i].charCodeAt(0)]) * BigInt(u) + BigInt(V[a[j ^ 1][i].charCodeAt(0)])) % M;
}
}
for (let k of range(0, 1)) {
for (let l = 1; l <= n; ++l) {
let t = L[k][l];
for (let r = n - l, j = l, f = !k ? 1 : 0; r; --r, ++j, f = !f ? 1 : 0) {
// console.log(t)
res.add((BigInt(t) * BigInt(P[r]) + BigInt(R[f][r])) % M)
t = (BigInt(t) * BigInt(u2) + BigInt(X[f][j])) % M
}
}
}
}
function main() {
P[0] = 1;
for (let i = 1; i < 608; ++i) {
P[i] = BigInt(P[i - 1]) * u2 % M;
}
for (let i = 0; i < 128; ++i) V[i] = i ^ i >> 1;
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
for (let pItr = p; pItr > 0; pItr--) {
a = [s1, s2];
shuffle(V, [V, 128]);
res.clear();
hh(n, a);
a[0] = a[0].split('').reverse().join('');
a[1] = a[1].split('').reverse().join('');
hh(n, a);

ws.write(res.size + "\n");
}
ws.end();
}```

### Gridland Provinces Solution in Scala

```import scala.reflect.ClassTag
object Solution {
import scala.io._
import scala.collection.mutable.TreeSet
var lineit:Iterator[String] = Source.stdin.getLines.filterNot(_.isEmpty).flatMap(i => i.split(" "))
def rs() : String = lineit.next
def ri() : Int = rs.toInt
val q1 = 82595483
val q2 = 82595479
val pow1 = Array.iterate[Int] (1, 1201)(i => (26 * i) % q1)
val pow2 = Array.iterate[Int] (1, 1201)(i => (26 * i) % q2)
/*
type HashCodes = Int
type HashCodesHash = Int
def hci (i: Int): HashCodes = {
i
}
def hcu (h: HashCodes, i: Int): HashCodes = {
((h * 26 + i) % q1)
}
def hcm (a: HashCodes, b: HashCodes, lb: Int): HashCodes = {
((a.toLong * pow1 (lb) + b) % q1).toInt
}
def hcl (a: HashCodes) = a
*/
type HashCodes = (Int, Int)
type HashCodesHash = Long
def hci (i: Int): HashCodes = {
(i, i)
}
def hcu (h: HashCodes, i: Int): HashCodes = {
((h._1 * 26 + i) % q1, (h._2 * 26 + i) % q2)
}
def hcm (a: HashCodes, b: HashCodes, lb: Int): HashCodes = {
( ((a._1.toLong * pow1 (lb) + b._1) % q1).toInt,
((a._2.toLong * pow2 (lb) + b._2) % q2).toInt)
}
def hcl (h: HashCodes): Long = (h._1.toLong << 32) | h._2.toLong
def ltos (l: Long): String = {
val sb = new StringBuilder ()
var x = l
while (x > 0) {
sb.append ((97 + (x % 26)).toChar)
x = x / 26
}
sb.toString.reverse
}
def powmod (x: Int, k: Int, q: Int) = {
var a = 1
var b = x
var p = k
while (p > 0) {
if ((p & 1) != 0) {
a = ((a.toLong * b.toLong) % q).toInt
}
b = ((b.toLong * b.toLong) % q).toInt
p = (p >> 1)
}
a
}
def test (n: Int, a: Array[String]): Int = {
val q = 354745078340568241L
//val q1 = 2147483629
//val q2 = 2147483647
val n2 = n * 2
val b = Array.tabulate (n2) (i => (a(i & 1)(i >> 1).toInt - 97))
def cycle (s: String) = {
var hc = (0 until n2).map (i => s(i).toInt - 97).foldLeft (hci (0)) (hcu)
for (o <- 0 until n2) {
//t += hcl ((0 until n2).map (i => s((i + o) % n2).toInt - 97).foldLeft (hci (0)) (hcu))
t += hcl (hc)
val c = s(o).toInt - 97
val q = hcm ( hci (c), hci (0), n2 - 1)
hc = hcu ( ((hc._1 - q._1 + q1) % q1, (hc._2 - q._2 + q2) % q2), c)
}
}
def path (c: Array[String]) {
val sb = new StringBuilder (n2)
var y = 0
for (i <- 0 until n2) {
sb.append (a(y)(i >> 1))
if ((i & 1) == 0) {
y ^= 1
}
}
val w = sb.toString.map(c => c.toInt - 97).toArray;
val suffix = Array.ofDim [HashCodes] (2, n+1)
val revsuffix = Array.ofDim [HashCodes] (2, n+1)

val prefix = Array.ofDim [HashCodes] (2, n+1)
val revprefix = Array.ofDim [HashCodes] (2, n+1)
for (k <- 0 to 1) {
val j = (c(k)(0).toInt - 97)
prefix(k)(0) = hci (j)
revprefix(k)(0) = hci (j)
suffix(k)(n) = hci (0)
revsuffix(k)(n) = hci (0)
for (x <- 1 until n) {
val i = (c(k)(x).toInt - 97)
prefix(k)(x) = hcu (prefix(k)(x-1), i)
revprefix(k)(x) = hcm ( hci(i), revprefix(k)(x-1), x)
}
for (x <- n - 1 to 0 by -1) {
val i = (c(k)(x).toInt - 97)
suffix(k)(x) =  hcm ( hci(i), suffix(k)(x+1), n - x - 1)
revsuffix(k)(x) =  hcu (revsuffix(k)(x+1), i)
}
}

var h1 = hci (0)
for (x <- 0 until n) {
var h2 = h1
for (y <- x until n) {
val k = y & 1
val h3 = hcm (h2, suffix(k)(y), n - y)
val h4 = hcm (h3, revsuffix (k^1)(y), n - y)
//Console.err.println ("x = %d, y = %d, h: %s, %s".format (x, y, h4.toString, ltos (h4._1)))
t += hcl (h4)
h2 = hcu (h2, w(2 * y))
h2 = hcu (h2, w(2 * y + 1))
}
val c1 = (c(0)(x).toInt - 97)
val c2 = (c(1)(x).toInt - 97)
h1 = revprefix (x & 1)(x)
h1 = hcm (h1, prefix ((x & 1) ^ 1)(x), x + 1)

//Console.err.println ("h1, %s".format (ltos (h1._1)))
//h1 = hcu (hcm ( (c1, c1), h1, 2 * x), c2)
}
}

def solve (b: Array[String]) = {
val z: String = b(0) + b(1).reverse
cycle (z)
path (b)
val tmp = b(0); b(0) = b(1); b(1) = tmp
path (b)
}

solve (a)
a(0) = a(0).reverse
a(1) = a(1).reverse
solve (a)
t.size
}
def main(args: Array[String]) {
val nt = ri
for (t <- 1 to nt) {
val n = ri
val a = Array (rs, rs)
println (test (n, a))
}
}
}```

### Gridland Provinces Solution in Pascal

Disclaimer: This problem (Gridland Provinces) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: HackerRank String Construction Solution