## Editorial for Cô gái chăn bò

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

#### Code mẫu của flashmt

const fi='';
fo='';
r:array[1..13] of longint=(0,1,2,4,5,8,9,10,16,17,18,20,21);
var num,i,m,n,re:longint;
a:array[0..1,0..31] of longint;
p:array[0..5] of longint;
d:array[0..31,0..31] of byte;

procedure init;
var i,j,k,max:longint; k1,k2:boolean;
begin
p[0]:=1;
for i:=1 to m do p[i]:=p[i-1]*2;
max:=p[m]-1;
fillchar(d,sizeof(d),0);
for i:=0 to max do
for j:=0 to max do
begin
k1:=false; k2:=false;
for k:=1 to 13 do
begin
if i and j=r[k] then k1:=true;
if i or j=max-r[k] then k2:=true;
end;
if k1 and k2 then
begin
d[i,j]:=1;
d[j,i]:=1;
end;
end;
end;

procedure pr;
var i,j,max,k,t:longint;
begin
if m>n then
begin
i:=m; m:=n; n:=i;
end;
init;
max:=p[m]-1;
dec(m);
t:=1;
fillchar(a,sizeof(a),0);
for i:=0 to max do a[1,i]:=1;
for i:=2 to n do
begin
t:=i mod 2;
for j:=0 to max do a[t,j]:=0;
for j:=0 to max do
for k:=0 to max do
if d[j,k]=1 then
a[t,j]:=a[t,j]+a[1-t,k];
end;
re:=0;
for i:=0 to max do
re:=re+a[t,i];
end;

begin
assign(input,fi);
reset(input);
assign(output,fo);
rewrite(output);
for i:=1 to num do
begin
pr;
writeln(re);
end;
close(input);
close(Output);
end.


#### Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

int f[40][160], m, n;

for(int i=1; i<n; ++i) {
if(a==b&&b==c&&c==d) return 0;
}
return 1;
}

int main() {
int tc; scanf("%d",&tc);
while(tc--) {
scanf("%d%d",&m,&n); if(m<n) swap(m,n);
for(int i = 2; i <= m; ++i)
}
}
unsigned long long res = 0;
for(int state = (1<<n)-1; state >= 0; --state) res += f[m][state];
printf("%llu\n", res);
}
return 0;
}


program cowgirl;
uses    math;

var     m,n,x:longint;
f:array[0..30,0..32] of longint;
check:array[0..32,0..32] of boolean;
inp:text;
Function GetBit(a,k:longint):longint;
begin
exit((a shr (k)) and 1);
end;

procedure init;
var     i,j,k:longint;
begin
x:=1;
for i:=1 to n do x:=x*2;
for i:=0 to 32 do
for j:=0 to 32 do  check[i,j]:=true;
for i:=0 to x-1 do
for j:=0 to x-1 do
for k:=0 to n-2 do
begin
if (getbit(i,k) = getbit(j,k)) and (getbit(i,k+1) = getbit(j,k+1)) and (getbit(i,k)=getbit(i,k+1))
then
begin
check[i,j]:=false;
end;

end;
end;

function process:longint;
var     row,i,j,k,x2:longint;
sum:int64;
begin
sum:=0;
x2:=1;
for i:=1 to m do x2:=x2*2;

if n=1 then exit(x2);
fillchar(f,sizeof(f),0);
for i:=0 to x do f[1,i]:=1;
for row:=2 to m do
for i:=0 to x-1 do
for j:=0 to x-1 do
begin
if check[i,j] then inc(f[row,j],f[row-1,i]);
end;
for i:=0 to x do inc(sum,f[m,i]);
exit(sum);
end;

procedure input;
var     t,sotest,i:longint;
begin
for i:=1 to sotest do
begin
if m<n then
begin
t:=m;
m:=n;
n:=t;
end;
init;
writeln(process);
end;
end;

begin
input;
end.


#### Code mẫu của RR

{\$R+,Q+}
PROGRAM COWGIRL;
CONST
maxn=30;
fi='';
fo='';
lt2:array[0..5] of integer=(1,2,4,8,16,32);
VAR
d:array[1..maxn,0..31] of longint;
ok:array[0..31,0..31] of integer;
m,n:integer;
f1,f2:text;
Procedure OpenFiles;
Begin
Assign(f1,fi); Reset(f1);
Assign(f2,fo); Rewrite(f2);
End;
Procedure CloseFiles;
Begin
Close(f1); Close(f2);
End;
Procedure WriteOutput;
Var
i:integer;
sl:longint;
Begin
sl:=0;
For i:=0 to lt2[m]-1 do
sl:=sl+d[n,i];
Writeln(f2,sl);
End;
Procedure Swap(var a,b:integer);
Var
temp:integer;
Begin
temp:=a; a:=b; b:=temp;
End;
Procedure Prepare;
Var
i,j,k,u,v:integer;
b:boolean;
Begin
For i:=0 to lt2[m]-1 do
For j:=0 to lt2[m]-1 do
begin
b:=true;
For k:=0 to m-2 do
begin
u:=(i shr k) and 3;
v:=(j shr k) and 3;
If (u or v=0) or (u and v=3) then
begin
b:=false;
break;
end;
end;
If b then ok[i,j]:=1 else ok[i,j]:=0;
end;
End;
Procedure Calculate;
Var
i,j,k:integer;
Begin
For j:=0 to lt2[m]-1 do
d[1,j]:=1;
For i:=2 to n do
For j:=0 to lt2[m]-1 do
begin
d[i,j]:=0;
For k:=0 to lt2[m]-1 do
If ok[j,k]=1 then d[i,j]:=d[i,j]+d[i-1,k];
end;
End;
Procedure Solve;
Var
t,i:integer;
Begin
For i:=1 to t do
begin
If m>n then Swap(m,n);
Prepare;
Calculate;
WriteOutput;
end;
End;
BEGIN
OpenFiles;
Solve;
CloseFiles;
END.


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <math.h>
int F(int m,int a,int b)
{
int A[6],B[6],i,t=1;
for(int i=1;i<=m;i++)
{
A[i]=a%2;
a=a/2;
B[i]=b%2;
b=b/2;
}
for(int i=1;i<m;i++)
{
if((A[i]==0&&B[i]==0&&A[i+1]==0&&B[i+1]==0)||(A[i]==1&&B[i]==1&&A[i+1]==1&&B[i+1]==1))
t=0;
}
return t;
}
main()
{
long T,n,m,KQ;
scanf("%ld",&T);
for(long i=0;i<T;i++)
{
KQ=0;
long f[33][33],thay,t;
scanf("%ld %ld",&n,&m);
if(n<m)
{
thay=n;
n=m;
m=thay;
}
t=pow(2,m);
for(long i=0;i<t;i++)
f[1][i]=1;
for(long i=2;i<=n;i++)
for(long j=0;j<t;j++)
{
f[i][j]=0;
for(long k=0;k<t;k++)
if(F(m,j,k)==1)
f[i][j]+=f[i-1][k];
}
for(long i=0;i<t;i++)
KQ+=f[n][i];
printf("%ld\n",KQ);
}
//getch();
}


#### Code mẫu của ll931110

Program COWGIRL;
Const
input  = '';
output = '';
maxn = 30;
maxd = 40;
Var
F: array[0..maxd,1..maxn] of longint;
m,n: longint;
t,i: longint;
fi,fo: text;

Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);

Assign(fo, output);
Rewrite(fo);
End;

Procedure optimize;
Var
i,j,k,res: longint;
a,b,c,d: longint;
x,y,tmp: longint;
ok: boolean;
Begin
Fillchar(F, sizeof(F), 0);

If m > n then
Begin
tmp:= m;
m:= n;
n:= tmp;
End;

For i:= 0 to 1 shl m - 1 do F[i,1]:= 1;

For i:= 2 to n do
For x:= 0 to 1 shl m - 1 do
For y:= 0 to 1 shl m - 1 do
Begin
ok:= true;
For k:= 0 to m - 2 do
Begin
If (x and (1 shl k)) = (1 shl k) then a:= 1 else a:= 0;
If (x and (1 shl (k + 1))) = (1 shl (k + 1)) then b:= 1 else b:= 0;

If (y and (1 shl k)) = (1 shl k) then c:= 1 else c:= 0;
If (y and (1 shl (k + 1))) = (1 shl (k + 1)) then d:= 1 else d:= 0;

tmp:= a + b + c + d;
If (tmp = 0) or (tmp = 4) then
Begin
ok:= false;
break;
End;
End;

If ok then F[x,i]:= F[x,i] + F[y,i - 1];
End;

res:= 0;
For i:= 0 to 1 shl m - 1 do res:= res + F[i,n];
Writeln(fo, res);
End;

Procedure closefile;
Begin
Close(fo);
Close(fi);
End;

Begin
openfile;

For i:= 1 to t do optimize;

closefile;
End.


#### Code mẫu của skyvn97

#include<stdio.h>
typedef unsigned long long ull;
ull res1[]={ 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, };
ull res2[]={ 14, 50, 178, 634, 2258, 8042, 28642, 102010, 363314, 1293962, 4608514, 16413466, 58457426, 208199210, };
ull res3[]={ 322, 2066, 13262, 85126, 546410, 3507314, 22512862, 144506294, };
ull res4[]={ 23858, 275690, 3185462, 36806846, };
ull res5[]={ 5735478, 119310334, };
int t,ct;
ull m,n,s;
int main(void)
{
scanf("%d",&t);
for (ct=1;ct<=t;ct=ct+1)
{
scanf("%llu",&m);
scanf("%llu",&n);
if (m>n)
{
s=m;m=n;n=s;
}
if (m==1) printf("%llu\n",res1[n-1]);
if (m==2) printf("%llu\n",res2[n-2]);
if (m==3) printf("%llu\n",res3[n-3]);
if (m==4) printf("%llu\n",res4[n-4]);
if (m==5) printf("%llu\n",res5[n-5]);
}
}


#### Code mẫu của khuc_tuan

def ok(a,b,c):
for i in range(c-1):
if (a&(1<<i))!=0 and (a&(1<<(i+1)))!=0 and (b&(1<<i))!=0 and (b&(1<<(i+1)))!=0:return False
if (a&(1<<i))==0 and (a&(1<<(i+1)))==0 and (b&(1<<i))==0 and (b&(1<<(i+1)))==0:return False
return True

f = [[[0 for xx in range(100)] for yy in range(10)] for zz in range(40)]
sum = [[0 for yy in range(10)] for zz in range(40)]
for i in range(1,31):
for j in range(1,6):
for bit in range(1<<j):
if i==1:f[i][j][bit]=1
else:
for b2 in range(1<<j):
if ok(bit,b2,j): f[i][j][bit] += f[i-1][j][b2]

for i in range(1,31):
for j in range(1,6):
for bit in range(1<<j):
sum[i][j] += f[i][j][bit]
st=input()
for i in range(st):
m,n=[int(xx) for xx in raw_input().split()]
if m>n:
t=m
m=n
n=t
print sum[n][m]