CodeEff/ECCO huggingface dataset:
# Original solution
import sys
def input():
	return sys.stdin.readline().strip()

N, A, B, K = list(map(int, input().split()))

mod = 998244353

fact_list = [1]
for i in range(1, N + 1):
	fact_list.append((fact_list[-1]*i) % mod)

def pow(x, y, mod=1000000007):
	pow_list = [x]
	i = 1
	while 2**i <= y:
		a = pow_list[-1]**2
		if mod != 0:
			a = a % mod
		pow_list.append(a)
		i += 1
	ans = 1
	for bit in range(len(pow_list)):
		if (2**bit) & y != 0:
			ans *= pow_list[bit]
			if mod != 0:
				ans = ans % mod
	return ans

def fact(n, mod=1000000007):
	return fact_list[n]
  
rev_list = [1]
for i in range(N):
  rev_list.append(pow(fact(i + 1, mod), mod - 2, mod))

def mod_rev(x, mod):
	"""
	関数powが必要
	"""
	return rev_list[x]


def comb(a, b, mod=1000000007):
	"""
	関数mod_rev, fact, powが必要
	"""
	if a < b or b < 0:
		return 0
	a_fact = fact(a, mod)
	b_fact = fact(b, mod)
	a_b_fact = fact(a - b, mod)
	if mod != 0:
		return (a_fact * mod_rev(b, mod) * mod_rev(a - b, mod))%mod
	else:
		return a_fact//(b_fact*a_b_fact)

ans = 0
for r in range(N + 1):
	rest = K - r * A
	if rest % B == 0 and rest // B >= 0 and rest // B <= N:
		b = rest // B
		ans += comb(N, r, mod)*comb(N, b, mod)
		ans %= mod

print(ans)

# Optimized solution

import sys
def input():
	return sys.stdin.readline().strip()

N, A, B, K = list(map(int, input().split()))

mod = 998244353

fact_list = [1]
for i in range(1, N + 1):
	fact_list.append((fact_list[-1]*i) % mod)

def pow(x, y, mod=1000000007):
	pow_list = [x]
	i = 1
	while 2**i <= y:
		a = pow_list[-1]**2
		if mod != 0:
			a = a % mod
		pow_list.append(a)
		i += 1
	ans = 1
	for bit in range(len(pow_list)):
		if (2**bit) & y != 0:
			ans *= pow_list[bit]
			if mod != 0:
				ans = ans % mod
	return ans

def fact(n, mod=1000000007):
	return fact_list[n]

inv_t = [0] + [1]
for i in range(2,N + 1):
	inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

def mod_rev(x, mod):
	"""
	関数powが必要
	"""
	return inv_t[x]

inv_fact = [1] + [1]

for i in range(2, N + 1):
	inv_fact.append((inv_fact[-1] * inv_t[i]) % mod)


def comb(a, b, mod=1000000007):
	"""
	関数mod_rev, fact, powが必要
	"""
	if a < b or b < 0:
		return 0
	if a == b or b == 0:
		return 1
	a_fact = fact(a, mod)
	b_fact = fact(b, mod)
	a_b_fact = fact(a - b, mod)
	if mod != 0:
		return (a_fact * inv_fact[b] * inv_fact[a - b])%mod
	else:
		return a_fact//(b_fact*a_b_fact)

ans = 0
times = 0
for r in range(N + 1):
	rest = K - r * A
	if rest % B == 0 and rest // B >= 0 and rest // B <= N:
		b = rest // B
		ans += comb(N, r, mod)*comb(N, b, mod)
		ans %= mod
		times += 1

print(ans)
# Original solution
# coding: utf-8
# Your code here!
import array

SIZE=300000; MOD= 998244353
#inv = array.array('q',[0]*(SIZE+1))# inv[j] = j^{-1} mod M
#fac = array.array('q',[0]*(SIZE+1))# inv[j] = j! mod M
#finv = array.array('q',[0]*(SIZE+1))# inv[j] = (j!)^{-1} mod M
inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod M
fac = [0]*(SIZE+1)# inv[j] = j! mod M
finv = [0]*(SIZE+1)# inv[j] = (j!)^{-1} mod M
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if r < 0 or r > n:
        return 0
    else:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    

n,a,b,k = [int(i) for i in input().split()]
ans=0
for i in range(n+1):
    if (k-i*a)%b == 0:
        ans = (ans + choose(n,i)*choose(n,(k-i*a)//b)%MOD)%MOD
print(ans)












# Optimized solution
SIZE=300000; MOD=998244353 #ここを変更する

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# inv[j] = j! mod MOD
finv = [0]*(SIZE+1)# inv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if r < 0 or r > n or n < 0:
        return 0
    else:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    

n,a,b,k = [int(i) for i in input().split()]
ans=0
for i in range(n+1):
    if (k-i*a)%b == 0:
        ans = (ans + choose(n,i)*choose(n,(k-i*a)//b)%MOD)%MOD
print(ans)
# Original solution
n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2,300003):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        n_c=min(n_a,n_b)
        n_a, n_b=n_a-min(n_a,n_b), n_b-min(n_a,n_b)
        count=0
        while n_a + n_b + n_c <=n and n_c>=0 and n_b>=0 and n_a>=0:
            ans+=com(n, n_c, mod) * com(n-n_c, n_b, mod) * com(n-n_c-n_b, n_a, mod) %mod

            n_c-=1
            n_b+=1
            n_a+=1

print((ans%mod))

# Optimized solution
n,a,b,k=[int(i) for i in input().split()]
c=a+b
mod=998244353
ans=0

g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  #逆元テーブル
inverse = [0, 1]  #逆元テーブル計算用テーブル

for i in range(2,300003):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

#以下のcom関数を用いて組み合わせを計算
def com(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

for i in range(n+1):
    if (k-b*i)%a==0 and k-b*i>=0:
        n_a=(k-b*i)//a
        n_b=i
        if  max(n_a, n_b) <=n:
            ans+=com(n, n_a, mod) * com(n, n_b, mod)  %mod

print((ans%mod))
# Original solution
from copy import deepcopy
dx=[0,0,1,-1]
dy=[1,-1,0,0]

def dfs(y,x,cnt):
    Ice_cp[y][x]=0
    cnt+=1
    for i in range(4):
        mx=x+dx[i]
        my=y+dy[i]
        if 0<=mx<m and 0<=my<n and Ice_cp[my][mx]==1:
            return dfs(my,mx,cnt)
    return cnt

while True:
    m=eval(input())
    n=eval(input())
    if n==m==0:break
    maxInt=0
    Ice=[list(map(int,input().split())) for i in range(n)]
    for i in range(n):
        for j in range(m):
            cnt=0
            Ice_cp=deepcopy(Ice)
            if Ice_cp[i][j]==1:
                maxInt=max(maxInt,dfs(i,j,cnt))
    print(maxInt)

# Optimized solution
dx=[0,0,1,-1]
dy=[1,-1,0,0]

def dfs(y,x,cnt):
    global maxInt
    maxInt=max(maxInt,cnt)
    Ice[y][x]=0
    for i in range(4):
        mx=x+dx[i]
        my=y+dy[i]
        if mx<0 or m<=mx or my<0 or n<=my:
            continue
        if Ice[my][mx]==1:
            dfs(my,mx,cnt+1)
            Ice[my][mx]=1

while True:
    m=eval(input())
    n=eval(input())
    if n==m==0:break
    maxInt=0
    Ice=[list(map(int,input().split())) for i in range(n)]
    for y in range(n):
        for x in range(m):
            if Ice[y][x]==1:
                dfs(y,x,1)
                Ice[y][x]=1
    print(maxInt)
# Original solution
def b(M,x,y,n=1):
 M[x][y]='0';t=[]
 if'1'==M[x-1][y]:t+=[b(M,x-1,y,n+1)]
 if'1'==M[x][y-1]:t+=[b(M,x,y-1,n+1)]
 if'1'==M[x+1][y]:t+=[b(M,x+1,y,n+1)]
 if'1'==M[x][y+1]:t+=[b(M,x,y+1,n+1)]
 M[x][y]='1'
 return max([n]+t)
for e in iter(input,'0'):
 n,m=int(e),int(eval(input()))
 P=[['0']*(n+2)for _ in[0]*(m+2)]
 for i in range(m):P[i+1][1:-1]=input().split()
 print((max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if'1'==P[i][j])))


# Optimized solution
def b(M,x,y,n=1):
 M[x][y]=0;t=[]
 if M[x-1][y]:t+=[b(M,x-1,y,n+1)]
 if M[x][y-1]:t+=[b(M,x,y-1,n+1)]
 if M[x+1][y]:t+=[b(M,x+1,y,n+1)]
 if M[x][y+1]:t+=[b(M,x,y+1,n+1)]
 M[x][y]=1
 return max([n]+t)
for e in iter(input,'0'):
 n,m=int(e),int(eval(input()))
 P=[[0]*(n+2)for _ in[0]*(m+2)]
 for i in range(m):P[i+1][1:-1]=list(map(int,input().split()))
 print((max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if P[i][j])))
# Original solution
def s():
 def b(M,x,y,n=0):
  if M[x][y]==0:return n
  M[x][y]=0
  a=max(b(M,x-1,y,n+1),b(M,x,y-1,n+1),b(M,x+1,y,n+1),b(M,x,y+1,n+1))
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(eval(input()))
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=list(map(int,input().split()))
  print((max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1))))
if'__main__'==__name__:s()


# Optimized solution
def s():
 def b(M,x,y,n):
  M[x][y]=0;a=n
  if M[x-1][y]:a=max(a,b(M,x-1,y,n+1))
  if M[x][y-1]:a=max(a,b(M,x,y-1,n+1))
  if M[x+1][y]:a=max(a,b(M,x+1,y,n+1))
  if M[x][y+1]:a=max(a,b(M,x,y+1,n+1))
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(eval(input()))
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=list(map(int,input().split()))
  print((max(b(P,i,j,1)for i in range(1,m+1)for j in range(1,n+1)if P[i][j])))
if'__main__'==__name__:s()
# Original solution
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:a=max(a,b(M,x-1,y,n+1))
  if M[x][y-1]:a=max(a,b(M,x,y-1,n+1))
  if M[x+1][y]:a=max(a,b(M,x+1,y,n+1))
  if M[x][y+1]:a=max(a,b(M,x,y+1,n+1))
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(eval(input()))
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=list(map(int,input().split()))
  print((max({b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if P[i][j]})))
if'__main__'==__name__:s()


# Optimized solution
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:
   t=b(M,x-1,y,n+1)
   if a<t:a=t
  if M[x][y-1]:
   t=b(M,x,y-1,n+1)
   if a<t:a=t
  if M[x+1][y]:
   t=b(M,x+1,y,n+1)
   if a<t:a=t
  if M[x][y+1]:
   t=b(M,x,y+1,n+1)
   if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(eval(input()))
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=list(map(int,input().split()))
  print((max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if P[i][j])))
if'__main__'==__name__:s()
# Original solution
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  for p,q in[(-1,0),(0,-1),(1,0),(0,1)]:
   if M[x+p][y+q]:
    t=b(M,x+p,y+q,n+1)
    if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(eval(input()))
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=list(map(int,input().split()))
  print((max(b(P,i,j)for i in range(1,m+1)for j in range(1,n+1)if P[i][j])))
if'__main__'==__name__:s()


# Optimized solution
def s():
 def b(M,x,y,n=1):
  M[x][y]=0;a=n
  if M[x-1][y]:
   t=b(M,x-1,y,n+1)
   if a<t:a=t
  if M[x][y-1]:
   t=b(M,x,y-1,n+1)
   if a<t:a=t
  if M[x+1][y]:
   t=b(M,x+1,y,n+1)
   if a<t:a=t
  if M[x][y+1]:
   t=b(M,x,y+1,n+1)
   if a<t:a=t
  M[x][y]=1
  return a
 for e in iter(input,'0'):
  n,m=int(e),int(eval(input()))
  P=[[0]*(n+2)for _ in[0]*(m+2)]
  for i in range(m):P[i+1][1:-1]=list(map(int,input().split()))
  a=0
  for i in range(1,m+1):
   for j in range(1,n+1):
    if P[i][j]:
     t=b(P,i,j)
     if a<t:a=t
  print(a)
if'__main__'==__name__:s()
# Original solution
def solve():
  while True:
    m, n  = int(eval(input())), int(eval(input()))
    if not m:
      break
    ices = [[0] + list(map(int,input().split())) + [0] for _ in range(n)]
    ices.insert(0, [0] * (m + 2),)
    ices.append([0] * (m + 2))
    score = [[0] * (m + 2) for _ in range(n + 2)]
    
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if ices[x][y]:
          score[x - 1][y] += 1
          score[x + 1][y] += 1
          score[x][y - 1] += 1
          score[x][y + 1] += 1
    
    def search(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = search(x - 1, y, imap, acc)
      if imap[x + 1][y]:
        b = search(x + 1, y, imap, acc)
      if imap[x][y - 1]:
        c = search(x, y - 1, imap, acc)
      if imap[x][y + 1]:
        d = search(x, y + 1, imap, acc)
      imap[x][y] = 1
      return max(acc, a, b, c, d)
    
    ans = 0
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if score[x][y] in [1, 2] and ices[x][y]:
          a = search(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()


# Optimized solution
def solve():
  while True:
    m, n  = int(eval(input())), int(eval(input()))
    if not m:
      break
    ices = [[0] + list(map(int,input().split())) + [0] for _ in range(n)]
    ices.insert(0, [0] * (m + 2),)
    ices.append([0] * (m + 2))
    score = [[0] * (m + 2) for _ in range(n + 2)]
    
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        score[x][y] = ices[x - 1][y] + ices[x + 1][y] + ices[x][y - 1] + ices[x][y + 1] 
    def search(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = search(x - 1, y, imap, acc)
      if imap[x + 1][y]:
        b = search(x + 1, y, imap, acc)
      if imap[x][y - 1]:
        c = search(x, y - 1, imap, acc)
      if imap[x][y + 1]:
        d = search(x, y + 1, imap, acc)
      imap[x][y] = 1
      return max(acc, a, b, c, d)
    
    ans = 0
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if score[x][y] in [1, 2] and ices[x][y]:
          a = search(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()
# Original solution
def solve():
  while True:
    m, n  = int(eval(input())), int(eval(input()))
    if not m:
      break
    ices = [[0] + list(map(int,input().split())) + [0] for _ in range(n)]
    ices.insert(0, [0] * (m + 2),)
    ices.append([0] * (m + 2))
    score = [[0] * (m + 2) for _ in range(n + 2)]
    
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        score[x][y] = ices[x - 1][y] + ices[x + 1][y] + ices[x][y - 1] + ices[x][y + 1] 
    def search(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = search(x - 1, y, imap, acc)
      if imap[x + 1][y]:
        b = search(x + 1, y, imap, acc)
      if imap[x][y - 1]:
        c = search(x, y - 1, imap, acc)
      if imap[x][y + 1]:
        d = search(x, y + 1, imap, acc)
      imap[x][y] = 1
      return max(acc, a, b, c, d)
    
    ans = 0
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if score[x][y] in [1, 2] and ices[x][y]:
          a = search(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()


# Optimized solution
def solve():
  while True:
    m, n  = int(eval(input())), int(eval(input()))
    if not m:
      break
    ices = [[0] + list(map(int,input().split())) + [0] for _ in range(n)]
    ices.insert(0, [0] * (m + 2),)
    ices.append([0] * (m + 2))
    score = [[0] * (m + 2) for _ in range(n + 2)]
    
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        score[x][y] = ices[x - 1][y] + ices[x + 1][y] + ices[x][y - 1] + ices[x][y + 1] 

    def search(x, y, imap, acc):
      imap[x][y] = 0
      acc += 1
      ret = acc
      a = b = c = d = 0
      if imap[x - 1][y]:
        a = search(x - 1, y, imap, acc)
        if ret < a:
          ret = a
      if imap[x + 1][y]:
        b = search(x + 1, y, imap, acc)
        if ret < b:
          ret = b
      if imap[x][y - 1]:
        c = search(x, y - 1, imap, acc)
        if ret < c:
          ret = c
      if imap[x][y + 1]:
        d = search(x, y + 1, imap, acc)
        if ret < d:
          ret = d
      imap[x][y] = 1
      return ret
    
    ans = 0
    for x in range(1, n + 1):
      for y in range(1, m + 1):
        if score[x][y] in [1, 2] and ices[x][y]:
          a = search(x, y, ices, 0)
          if ans < a:
            ans = a
    
    print(ans)

solve()
# Original solution
from copy import deepcopy
from array import array

while True:
    m = int(input())
    n = int(input())

    if m == 0 and n == 0:
        break

    begin = [array('b', [False] * m) for y in range(n)]

    for y in range(n):
        line = list(map(int, input().split(' ')))
        for x in range(m):
            if line[x] == 1:
                begin[y][x] = True

    # (stage, current position(x, y), current point)
    que = []
    for x in range(m):
        for y in range(n):
            if begin[y][x]:
                stage = deepcopy(begin)
                stage[y][x] = False
                que.append((stage, (x, y), 1))


    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    ans = 0

    while que:
        stage = que.pop()
        for i in range(4):
            nx = dx[i] + stage[1][0]
            ny = dy[i] + stage[1][1]
            if 0 <= nx < m and 0 <= ny < n and stage[0][ny][nx]:
                field = deepcopy(stage[0])
                field[ny][nx] = False
                ans = max(ans, stage[2] + 1)
                que.append((field, (nx, ny), stage[2] + 1))

    print(ans)

# Optimized solution
from copy import deepcopy

while True:

    m = int(input())
    n = int(input())

    if m == 0 and n == 0:
        break

    field = [[False] * m for y in range(n)]

    for y in range(n):
        line = list(map(int, input().split(' ')))
        for x in range(m):
            if line[x] == 1:
                field[y][x] = True

    ans = 0

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    def search(x, y, d):
        global ans

        if d > ans:
            ans = d

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < m and 0 <= ny < n and field[ny][nx]:
                field[ny][nx] = False
                search(nx, ny, d + 1)
                field[ny][nx] = True

    for x in range(m):
        for y in range(n):
            if field[y][x]:
                field[y][x] = False
                search(x, y, 1)
                field[y][x] = True

    print(ans)
# Original solution
from collections import deque
while 1:
    c = eval(input())
    r = eval(input())
    if c == 0: break
    l = [list(map(int, input().split())) for i in range(r)]
    ans = 0
    d = [(-1,0),(0,-1),(1,0),(0,1)]
    for i in range(c):
        for j in range(r):
            q = deque()
            a = [[0]*c for x in range(r)]
            if l[j][i] == 0: continue
            a[j][i] = 1
            q.append((j,i))
            while len(q) != 0:
                cy, cx = q.popleft()
                for x, y in d:
                    dx = x + cx; dy = y + cy;
                    if 0<=dx<c and 0<=dy<r and a[dy][dx] == 0 and l[dy][dx] == 1:
                        q.append((dy, dx))
                        a[dy][dx] = a[cy][cx] + 1
            for i in range(c):
                for j in range(r):
                    ans = max(ans, a[j][i])
    print(ans)

# Optimized solution
while 1:
    c = eval(input())
    r = eval(input())
    if c == 0: break        
    l = [list(map(int, input().split())) for i in range(r)]
    ans = 0
    d = [(-1,0),(0,-1),(1,0),(0,1)]
    def dfs(j, i, cnt):
        global ans
        ans = max(ans, cnt)
        for x, y in d:
            dx = x + i; dy = y + j
            if 0<=dx<c and 0<=dy<r and l[dy][dx]:
                l[dy][dx] = False
                dfs(dy, dx, cnt+1)
                l[dy][dx] = True
    for i in range(c):
        for j in range(r):
            if l[j][i]:
                l[j][i] = False
                dfs(j,i,1)
                l[j][i] = True
    print(ans)
# Original solution
def rotate(p, comm):
    if comm==0:
        p[0],p[1],p[2], p[27],p[28],p[29] = p[27],p[28],p[29], p[0],p[1],p[2]
        p[14], p[15] = p[15], p[14]
        p[18], p[20] = p[20], p[18]
    elif comm==1:
        p[2],p[5],p[8], p[21],p[24],p[27] = p[21],p[24],p[27], p[2],p[5],p[8]
        p[11], p[18] = p[18], p[11]
        p[12], p[14] = p[14], p[12]
    elif comm==2:
        p[6],p[7],p[8], p[21],p[22],p[23] = p[21],p[22],p[23], p[6],p[7],p[8]
        p[12], p[17] = p[17], p[12]
        p[9], p[11] = p[11], p[9]
    elif comm==3:
        p[0],p[3],p[6], p[23],p[26],p[29] = p[23],p[26],p[29], p[0],p[3],p[6]
        p[9], p[20] = p[20], p[9]
        p[15], p[17] = p[17], p[15]
def all_eq(A, left, right):
    return all(A[i]==A[left] for i in range(left, right))
def is_correct(p):
    return all_eq(p, 9, 12) and all_eq(p, 12, 15) and all_eq(p, 15, 18) and all_eq(p, 18, 21) and all_eq(p, 0, 9) and all_eq(p, 21, 30)
def dfs(p, cnt, f):
    ret = 9
    if cnt==9:
        return 9
    if is_correct(p):
        return cnt
    for k in range(4):
        if k==f:
            continue
        rotate(p, k)
        ret = min(ret, dfs(p, cnt+1, k))
        rotate(p, k)
    return ret

n = eval(input())
for _ in range(n):
    p = list(map(int, input().split()))
    print(dfs(p, 0, -1))

# Optimized solution
def rotate(p, comm):
    if comm==0:
        p[0],p[1],p[2], p[27],p[28],p[29] = p[27],p[28],p[29], p[0],p[1],p[2]
        p[14], p[15] = p[15], p[14]
        p[18], p[20] = p[20], p[18]
    elif comm==1:
        p[2],p[5],p[8], p[21],p[24],p[27] = p[21],p[24],p[27], p[2],p[5],p[8]
        p[11], p[18] = p[18], p[11]
        p[12], p[14] = p[14], p[12]
    elif comm==2:
        p[6],p[7],p[8], p[21],p[22],p[23] = p[21],p[22],p[23], p[6],p[7],p[8]
        p[12], p[17] = p[17], p[12]
        p[9], p[11] = p[11], p[9]
    elif comm==3:
        p[0],p[3],p[6], p[23],p[26],p[29] = p[23],p[26],p[29], p[0],p[3],p[6]
        p[9], p[20] = p[20], p[9]
        p[15], p[17] = p[17], p[15]
def all_eq(A, left, right):
    return all(A[i]==A[left] for i in range(left, right))
def is_correct(p):
    return all_eq(p, 9, 12) and all_eq(p, 12, 15) and all_eq(p, 15, 18) and all_eq(p, 18, 21) and all_eq(p, 0, 9) and all_eq(p, 21, 30)
ans = 8
def dfs(p, cnt, f):
    global ans
    if cnt>ans:
        return
    if is_correct(p):
        ans = cnt
        return
    for k in range(4):
        if k==f:
            continue
        rotate(p, k)
        dfs(p, cnt+1, k)
        rotate(p, k)

n = eval(input())
for _ in range(n):
    p = list(map(int, input().split()))
    ans = 8
    dfs(p, 0, -1)
    print(ans)