You are given a binary matrix $A$ of size $n \times n$. Let's denote an $x$-compression of the given matrix as a matrix $B$ of size $\frac{n}{x} \times \frac{n}{x}$ such that for every $i \in [1, n], j \in [1, n]$ the condition $A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]$ is met.

Obviously, $x$-compression is possible only if $x$ divides $n$, but this condition is not enough. For example, the following matrix of size $2 \times 2$ does not have any $2$-compression:

 $01$   $10$ 

For the given matrix $A$, find maximum $x$ such that an $x$-compression of this matrix is possible.

Note that the input is given in compressed form. But even though it is compressed, you'd better use fast input.


-----Input-----

The first line contains one number $n$ ($4 \le n \le 5200$) — the number of rows and columns in the matrix $A$. It is guaranteed that $n$ is divisible by $4$.

Then the representation of matrix follows. Each of $n$ next lines contains $\frac{n}{4}$ one-digit hexadecimal numbers (that is, these numbers can be represented either as digits from $0$ to $9$ or as uppercase Latin letters from $A$ to $F$). Binary representation of each of these numbers denotes next $4$ elements of the matrix in the corresponding row. For example, if the number $B$ is given, then the corresponding elements are 1011, and if the number is $5$, then the corresponding elements are 0101.

Elements are not separated by whitespaces.


-----Output-----

Print one number: maximum $x$ such that an $x$-compression of the given matrix is possible.


-----Examples-----
Input
8
E7
E7
E7
00
00
E7
E7
E7

Output
1

Input
4
7
F
F
F

Output
1



-----Note-----

The first example corresponds to the matrix:  $11100111$   $11100111$   $11100111$   $00000000$   $00000000$   $11100111$   $11100111$   $11100111$ 

It is easy to see that the answer on this example is $1$.

Difficulty: interview

Starter code:

Solutions:
(lambda R:(lambda N:(lambda n:any((lambda z,r:all((lambda p:all(p==k for k in n[j:j+i]))(n[j])for j in range(0,N,i))and all(all((lambda q:q==z or q==r)(j[k:k+i])for k in range(0,N,i))for j in n)and[print(i)])('0'*i,'1'*i)for i in range(N,0,-1)if N%i==0))([bin(int(R(),16))[2:].zfill(N)for i in range(N)]))(int(R())))(__import__('sys').stdin.readline)

n=int(input())
MAT=[format(int(input(),16),"b").zfill(n) for i in range(n)]

R=[]

NOW=1
for i in range(1,n):
    if MAT[i]==MAT[i-1]:
        NOW+=1
    else:
        R.append(NOW)
        NOW=1

R.append(NOW)

C=[]
def matchcol(i):
    for j in range(n):
        if MAT[j][i-1]!=MAT[j][i]:
            return 0
    else:
        return 1

NOW=1
for i in range(1,n):
    if matchcol(i):
        NOW+=1
    else:
        C.append(NOW)
        NOW=1

C.append(NOW)

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

ANS=R[0]
for x in R+C:
    ANS=gcd(ANS,x)

print(ANS)
        
    
    


from math import gcd

n = int(input())
a = []
for i in range(n):
    row = input()
    a.append(bin(int(row,16))[2:].zfill(n))
# print(*a, sep='\n')
to_vis = [0]*n
ans = n
for i in range(n):
    br = False
    j = to_vis[i]
    while j < n:
        # print('j', j)
        currx = 1
        d = a[i][j]
        expand = True
        while expand and currx+i < n and currx+j < n:
            for ki in range(i, i+currx+1):
                if a[ki][j+currx] != d:
                    expand = False
                    break
            if expand:
                for kj in range(j, j+currx+1):
                    if a[i+currx][kj] != d:
                        expand = False
                        break
            if expand:
                currx += 1
        for ki in range(i, i+currx):
            if to_vis[ki] == j:
                to_vis[ki] = j+currx
        # print(currx)
        ans = gcd(ans, currx)
        if ans == 1:
            br = True
            break
        j += currx
        # print(to_vis)
    if br:
        break

print(ans)


def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

n = int(input())
ans = n
c = 0
pre = ""
for i in range(n):
    s = bin((1<<n)+int(input(),16))[3:]
    if i == 0 or s != pre:
        pre = s
        ans = gcd(ans, c)
        # print("c",c,"ans",ans)
        c = 1
        cc = 1
        for j in range(1, n):
            if s[j] == s[j-1]:
                cc += 1
            else:
                ans = gcd(ans, cc)
                # print("cc",cc,"ans",ans)
                cc = 1
                
    else:
        c += 1
    
ans = gcd(ans, c)
# print(s)
print(ans)


import sys

hex2bin = ['']*256
hex2bin[ord('0')] = '0000'
hex2bin[ord('1')] = '0001'
hex2bin[ord('2')] = '0010'
hex2bin[ord('3')] = '0011'
hex2bin[ord('4')] = '0010'
hex2bin[ord('5')] = '0010'
hex2bin[ord('6')] = '0110'
hex2bin[ord('7')] = '0111'
hex2bin[ord('8')] = '1000'
hex2bin[ord('9')] = '1001'
hex2bin[ord('A')] = '0010'
hex2bin[ord('B')] = '0010'
hex2bin[ord('C')] = '1100'
hex2bin[ord('D')] = '0010'
hex2bin[ord('E')] = '1110'
hex2bin[ord('F')] = '1111'


n = int(input())

buckets = [0]*(n+1)

inp = sys.stdin.read().splitlines()

prev = ''
count = 0
for i in range(n):
    if inp[i]==prev:
        count += 1
    else:
        buckets[count] += 1
        count = 1
        prev = inp[i]

        prev_c = ''
        counter = 0
        for hexx in prev:
            for c in hex2bin[ord(hexx)]:
                if c==prev_c:
                    counter += 1
                else:
                    buckets[counter] += 1
                    counter = 1
                    prev_c = c
        buckets[counter] += 1
    if buckets[1]!=0 or (buckets[2]!=0 and buckets[3]!=0):
        print(1)
        return

buckets[count] += 1

x = 0
for i in range(1,n+1):
    if buckets[i]:
        while i:
            i,x=x%i,i
print(x)

from sys import stdin,stdout
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
n=int(stdin.readline())
temp=""
ans=n
p=0
for i in range(n):
    s=bin((1<<n)+int(stdin.readline(),16))[3:]
    if i==0 or temp!=s:
        temp=s
        ans=gcd(ans,p)
        p=1
        pp=1
        for j in range(1,n):
            if s[j]==s[j-1]:
                pp+=1
            else:
                ans=gcd(ans,pp)
                pp=1
    else:
        p+=1
ans=gcd(ans,p)
print(ans)

from sys import stdin,stdout
def hexa(c):
	if c=='0':
		return "0000"
	if c=='1':
		return "0001"
	if c=='2':
		return "0010"
	if c=='3':
		return "0011"
	if c=='4':
		return "0100"
	if c=='5':
		return "0101"
	if c=='6':
		return "0110"
	if c=='7':
		return "0111"
	if c=='8':
		return "1000"
	if c=='9':
		return "1001"
	if c=='A':
		return "1010"
	if c=='B':
		return "1011"
	if c=='C':
		return "1100"
	if c=='D':
		return "1101"
	if c=='E':
		return "1110"
	if c=='F':
		return "1111"
#hexa = ['0000','0001','0010','0011','0100','0101','0110','0111','1000','1001','1010','1011','1100','1101','1110','1111']
def gcd(a,b):
	if b==0:
		return a
	return gcd(b,a%b)

n=int(stdin.readline())
a=[0]*n
for _ in range(n):
	s = stdin.readline().strip()
	t=""
	for i in s:
		
		t+=hexa(i)
	a[_] = t

r=[]
t= 1
for i in range(1,n):
	if a[i]==a[i-1]:
		t+=1
	else:
		r.append(t)
		t=1
r.append(t)

c=[]
t=1
for i in range(1,n):
	f=1
	for j in range(n):
		if a[j][i-1]!=a[j][i]:
			f=0
			break
	if f==1:
		t+=1
	else:
		c.append(t)
		t=1
c.append(t)

ans = r[0]
for i in r+c:
	ans = gcd(ans,i)

stdout.write("%d" %ans)


from sys import stdin,stdout

def gcd(a,b):
	if b==0:
		return a
	return gcd(b,a%b)

n=int(stdin.readline())
a=[0]*n
for _ in range(n):
	a[_] = format(int(stdin.readline().strip(),16),"b").zfill(n)
	

r=[]
t= 1
for i in range(1,n):
	if a[i]==a[i-1]:
		t+=1
	else:
		r.append(t)
		t=1
r.append(t)

c=[]
t=1
for i in range(1,n):
	f=1
	for j in range(n):
		if a[j][i-1]!=a[j][i]:
			f=0
			break
	if f==1:
		t+=1
	else:
		c.append(t)
		t=1
c.append(t)

ans = r[0]
for i in r+c:
	ans = gcd(ans,i)

stdout.write("%d" %ans)


import sys
n = int(sys.stdin.readline())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = bin((1 << n) | int(sys.stdin.readline(), 16))[3:]

from math import gcd
ans = 0
i = 0
while i < n:
    j = i + 1
    while j < n and a[i] == a[j]:
        j += 1
    ans = gcd(ans, j - i)
    k = 0
    while k < n:
        l = k + 1
        while l < n and a[i][k] == a[i][l]:
            l += 1
        ans = gcd(ans, k - l)
        k = l
    i = j
    
print(ans)


from math import gcd
from functools import reduce
import sys
import os 
d=sys.stdin.readlines()
if d[-1][-1] != "\n":
    d[-1]+="\n"

n = int(d[0])
cur_tab = [0 for _ in range(n+1)]

def group(l):
    cur = 1
    for x in range(1,n):
        if l[x] == l[x-1]:
            cur+=1
        else:
            cur_tab[cur]=1
            cur=1
    cur_tab[cur]=1


mat=[None for _ in range(n)]
euh=0

for x in d[1:]:
    line = x[:-1]
    s=str(bin(int(line, 16)))[2:].zfill(n)
    mat[euh]=s
    euh+=1
    group(s)
for i in range(n):
    cur=1
    for x in range(1,n):
        if mat[x][i] == mat[x-1][i]:
            cur+=1
        else:
            cur_tab[cur]=1
            cur=1
    cur_tab[cur]=1
print(reduce(gcd, [index for index in range(n+1) if cur_tab[index] == 1]))

from math import gcd
from functools import reduce
import sys
import os 
d=sys.stdin.readlines()
if d[-1][-1] != "\n":
    d[-1]+="\n"

n = int(d[0])
cur_tab = [0 for _ in range(n+1)]

def group(l):
    cur = 1
    for x in range(1,n):
        if l[x] == l[x-1]:
            cur+=1
        else:
            cur_tab[cur]=1
            cur=1
    cur_tab[cur]=1
    if cur_tab[1]==1:
        print(1)
        return


mat=[None for _ in range(n)]
euh=0

for x in d[1:]:
    line = x[:-1]
    s=str(bin(int(line, 16)))[2:].zfill(n)
    mat[euh]=s
    euh+=1
    group(s)
for i in range(n):
    cur=1
    for x in range(1,n):
        if mat[x][i] == mat[x-1][i]:
            cur+=1
        else:
            cur_tab[cur]=1
            cur=1
    cur_tab[cur]=1
    if cur_tab[1]==1:
        print(1)
        return
print(reduce(gcd, [index for index in range(n+1) if cur_tab[index] == 1]))

from math import gcd
from functools import reduce
import sys
import os 
d=sys.stdin.readlines()


n = int(d[0])
cur_tab = [0 for _ in range(n+1)]

def group(l):
    cur = 1
    for x in range(1,n):
        if l[x] == l[x-1]:
            cur+=1
        else:
            cur_tab[cur]=1
            cur=1
    cur_tab[cur]=1
    if cur_tab[1]==1:
        print(1)
        return


mat=[None for _ in range(n)]
euh=0

for x in d[1:]:
    line = x[:-1]
    s=str(bin(int(line, 16)))[2:].zfill(n)
    mat[euh]=s
    euh+=1
    group(s)
    
for i in range(n):
    cur=1
    for x in range(1,n):
        if mat[x][i] == mat[x-1][i]:
            cur+=1
        else:
            cur_tab[cur]=1
            cur=1
    cur_tab[cur]=1
    if cur_tab[1]==1:
        print(1)
        return
print(reduce(gcd, [index for index in range(n+1) if cur_tab[index] == 1]))

from math import gcd
from functools import reduce
import sys
import os 
d=sys.stdin.readlines()

class Tab(object):
    def __init__(self):
        self.value = [0 for _ in range(n+1)]
    
    def set_one(self, ind):
        if ind==1:
            print(1)
            return
        else:
            self.value[ind]=1
    
    def ones(self):
        return [index for index in range(n+1) if self.value[index] == 1]

n = int(d[0])
cur_tab = Tab()


def group(l):
    cur = 1
    for x in range(1,n):
        if l[x] == l[x-1]:
            cur+=1
        else:
            cur_tab.set_one(cur)
            cur=1
    cur_tab.set_one(cur)


mat=[None for _ in range(n)]
euh=0

for x in d[1:]:
    line = x[:-1]
    s=str(bin(int(line, 16)))[2:].zfill(n)
    mat[euh]=s
    euh+=1
    group(s)
for i in range(n):
    cur=1
    for x in range(1,n):
        if mat[x][i] == mat[x-1][i]:
            cur+=1
        else:
            cur_tab.set_one(cur)
            cur=1
    cur_tab.set_one(cur)
print(reduce(gcd, cur_tab.ones()))

from math import gcd
from functools import reduce
import sys
import os 
# Testing burritos code
d=sys.stdin.read().splitlines()

class Tab(object):
    def __init__(self):
        self.value = [0 for _ in range(n+1)]
    
    def set_one(self, ind):
        if ind==1:
            print(1)
            return
        else:
            self.value[ind]=1
    
    def ones(self):
        return [index for index in range(n+1) if self.value[index] == 1]

n = int(d[0])
cur_tab = Tab()


def group(l):
    cur = 1
    for x in range(1,n):
        if l[x] == l[x-1]:
            cur+=1
        else:
            cur_tab.set_one(cur)
            cur=1
    cur_tab.set_one(cur)


mat=[None for _ in range(n)]
euh=0

for line in d[1:]:
    s=str(bin(int(line, 16)))[2:].zfill(n)
    mat[euh]=s
    euh+=1
    group(s)
for i in range(n):
    cur=1
    for x in range(1,n):
        if mat[x][i] == mat[x-1][i]:
            cur+=1
        else:
            cur_tab.set_one(cur)
            cur=1
    cur_tab.set_one(cur)
print(reduce(gcd, cur_tab.ones()))

from math import gcd
import sys
n = int(sys.stdin.readline())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = bin((1 << n) | int(sys.stdin.readline(), 16))[3:]


ans, i = 0, 0
while i < n:
    j = i + 1
    while j < n and a[i] == a[j]:
        j += 1
    ans = gcd(ans, j - i)

    k = 0
    while k < n:
        l = k + 1
        while l < n and a[i][k] == a[i][l]:
            l += 1
        ans = gcd(ans, abs(l - k))
        k = l
    i = j
print(ans)


import sys
from math import gcd

n = int(sys.stdin.readline())
matrix = [[] for _ in range(n)]
for i in range(n):
	matrix[i] = bin((1<<n) | int(sys.stdin.readline(), 16))[3:]

ans = 0
i = 0

while(i<n):
	j = i+1
	while(j<n and matrix[i]==matrix[j]): #Recorro por filas
		j+=1
	ans = gcd(ans,j-i)

	col = 0
	while(col<n):
		l = col + 1
		while(l<n and matrix[i][col]==matrix[i][l]): #Recorro por columnas
			l+=1
		ans = gcd(ans, col-l)
		col = l
	i = j

print(ans)

from math import gcd
def D():

	n = int(input())
	matrix = [0 for _ in range(n)]
	for i in range(n):
		a = bin(int(input(), 16))[2:]
		matrix[i] = '0'*(n-len(a))+ a

	ans = 0
	i = 0

	while(i<n):
		j = i+1
		while(j<n and matrix[i]==matrix[j]): #Recorro por filas
			j+=1
		ans = gcd(ans,j-i)

		col = 0
		while(col<n):
			l = col + 1
			while(l<n and matrix[i][col]==matrix[i][l]): #Recorro por columnas
				l+=1
			ans = gcd(ans, col-l)
			col = l
		i = j

	print(ans)

D()

import sys
from math import gcd
n = int(sys.stdin.readline())
matrix = [[] for _ in range (n)]
for i in range (n) : matrix[i] = bin((1 << n) | int(sys.stdin.readline(), 16))[3:]
i = ans = 0
while i < n :
	j = i + 1
	while j < n and matrix[i] == matrix[j] : j += 1
	ans = gcd(ans, j - i)
	col = 0
	while col < n :
		l = col + 1
		while l < n and matrix[i][col] == matrix[i][l] : l += 1
		ans = gcd(ans, col - l)
		col = l
	i = j
print(ans)