Let's assume that we are given a matrix b of size x × y, let's determine the operation of mirroring matrix b. The mirroring of matrix b is a 2x × y matrix c which has the following properties:

  the upper half of matrix c (rows with numbers from 1 to x) exactly matches b;  the lower half of matrix c (rows with numbers from x + 1 to 2x) is symmetric to the upper one; the symmetry line is the line that separates two halves (the line that goes in the middle, between rows x and x + 1). 

Sereja has an n × m matrix a. He wants to find such matrix b, that it can be transformed into matrix a, if we'll perform on it several (possibly zero) mirrorings. What minimum number of rows can such matrix contain?


-----Input-----

The first line contains two integers, n and m (1 ≤ n, m ≤ 100). Each of the next n lines contains m integers — the elements of matrix a. The i-th line contains integers a_{i}1, a_{i}2, ..., a_{im} (0 ≤ a_{ij} ≤ 1) — the i-th row of the matrix a.


-----Output-----

In the single line, print the answer to the problem — the minimum number of rows of matrix b.


-----Examples-----
Input
4 3
0 0 1
1 1 0
1 1 0
0 0 1

Output
2

Input
3 3
0 0 0
0 0 0
0 0 0

Output
3

Input
8 1
0
1
1
0
0
1
1
0

Output
2



-----Note-----

In the first test sample the answer is a 2 × 3 matrix b:



001

110



If we perform a mirroring operation with this matrix, we get the matrix a that is given in the input:



001

110

110

001

Difficulty: interview

Starter code:

Solutions:
n,m = [int(i) for i in input().split()]
l = []
for i in range(n):
    l.append(input().strip())
while len(l)%2 == 0:
    mirror = True
    for i in range(len(l)//2):
        if l[i] != l[len(l)-1-i]:
            mirror = False
            break
    if mirror:
        l = l[:len(l)//2]
    else:
        break

print(len(l))


n,m=map(int,input().split())
a=[]
for i in range(n):
    a.append(''.join(input().split()))
while n%2==0:
    k=0
    for i in range(n//2):
        if a[i]==a[n-i-1]:
            k+=1
    if k!=n//2:
        break
    n=n//2
print(n)

def can_mirror(matrix):
    if len(matrix) % 2 != 0:
        return False
    mid = len(matrix) // 2
    for i in range(mid):
        lower = -i-1
        if matrix[mid+lower] != matrix[mid+i]:
            return False
    return True


def mirror(matrx):
    mid = len(matrix) // 2
    return matrix[:mid]


n, m = list(map(int, input().split()))
matrix = []
for i in range(n):
    matrix.append(list(map(int, input().split())))
while can_mirror(matrix):
    matrix = mirror(matrix)
print(len(matrix))


def check(n, m, a):
    for i in range(n // 2):
        for j in range(m):
            if a[i][j] != a[-i - 1][j]:
                return 0
    if n % 2:
        return 0
    return 1

def new(n, a):
    return a[:(n + 1) // 2]

n, m = map(int, input().split())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
cnt = 0
while (not (n % 2)) and check(n, m, a):
    a = new(n, a)
    n //= 2
print(len(a))

from sys import stdin

def isreversed(a):
    if(len(a) % 2 == 0):
        if(a[:len(a) // 2] == a[len(a) // 2:][::-1]):
            return True
    return False

a = []
n, m = list(map(int, stdin.readline().split()))
for i in range(n):
    a.append(list(map(int, stdin.readline().split())))
res = n
while(isreversed(a)):
    res //= 2
    a = a[:len(a) // 2]
print(res)

n,m=map(int,input().split())
matrix=[]

for i in range(n):
    matrix.append([int(x) for x in input().split()])

def mirror(matrix):
    mirrormatrix=matrix[:]
    matrix.reverse()
    mirrormatrix+=matrix[:]
    matrix.reverse()
    return mirrormatrix

while True:
    if len(matrix)%2==0:
        if mirror(matrix[:int(len(matrix)/2)])==matrix:
            matrix=matrix[:int(len(matrix)/2)]
        else:
            print(len(matrix))
            break
    else:
        print(len(matrix))
        break

n, m = map(int, input().split())

ans = n

arr = []
for i in range(n):
    arr.append(input())

while True:
    if n & 1:
        print(ans)
        break
    else:
        k = n // 2
        for i in range(k):
            if arr[i] != arr[n - i - 1]:
                print(ans)
                return
        n = k
        ans = n

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

def pol(x, y):
  if y % 2 != 0:
    return False
  l, r = 0, y - 1
  while l < r:
    if a[l][x] != a[r][x]:
      return False
    l += 1
    r -= 1
  return True
result = 1
for i in range(m):
  j = n
  while pol(i, j):
    j //= 2
  result = max(result, j)
print(result)

def symetry(a,n,m):
   symmetry = 0
   k = n // 2
   for x in range(n):
        for y in range(m):
             k = n - x - 1 
             if k < n - 1 and a[x][y] != a[k][y]:
                  symmetry = 1
   return symmetry 
      
n, m = list(map(int, input().split()))
list_anmi = [list(map(int, input().split())) for i in range(n)]
sym = 0
while n % 2 == 0:   
  if symetry(list_anmi[0 : n],n,m) == 0:
     n = n // 2
  else:
      break
sym = n
print(sym)


n, m = [int(i) for i in input().split()]
a = []
for i in range(n):
    a.append(input())
result = n
flag = True
while n % 2 == 0:
    n = int(n / 2)
    x1 = n
    x2 = n + 1
    while x1 > 0:
        if a[x1 - 1] != a[x2 - 1]:
            flag = False
            break
        x1 -= 1
        x2 += 1
    if flag == False:
        break
    result = n


print(result)


# =__='

n, m = list(map(int, input().split()))
a = []
for i in range(n):
    a.append(input())

b = (n % 2 == 0)
while (b):
    b = True
    for i in range(n // 2):
        if (a[i] != a[n - i - 1]):
            b = False
            break
    
    b = b and (n % 2 == 0)
    if (b):
        n = n // 2

print(n)


def check(i, j):
    nonlocal a
    while i < j:
        if a[i] != a[j]:
            return False
        i += 1
        j -= 1
    return True
n, m = map(int, input().split())
a = []
for i in range(n):
    a.append(input().strip())
last = n
while last % 2 == 0:
    if check(0, last - 1):
        last //= 2
    else:
        break
print(last)

def checkMatr(a):
    res = True
    ln = len(a)
    hln = int(ln/2)
    if ln % 2 != 0:
        res = False
    else:
        for i in range(hln):
            if a[i] != a[ln-1-i]:
                res = False
    return res

n, m = list(map(int, input().split()))
table = []
for i in range(n):
    table.append(str(input()))

while checkMatr(table):
    table = table[:int(len(table)/2)]

print(len(table))



def pretty_print_list(a):
    for aa in a:
        print(*aa)


        
m, n = list(map(int, input().split()))
a = [[i for i in map(int, input().split())] for _ in range(m)]

#pretty_print_list(a)

if m % 2:
    print(m)
    return
'''    
for i in range(m):
    print(i, a[i])
    print(-i, a[m - i - 1])
'''
    
#return
m2 = m
while not m2 % 2:
    m2 //= 2
    for i in range(m2):
        #print(a[i], a[-i])
        #print(i, a[i])
        #if a[i] != a[-i]:
        if a[i] != a[2 * m2 - i - 1]:
            print(m2 * 2)
            return
print(m2)



import sys
n,m = list(map(int,input().split()))
a=[]
for i in range(n):
	a.append(''.join(input().split()))
if n==1:
	print(1)
	return
if n%2:
	print(n)
	return
d=n//2
small=n
while d:
	i=d-1
	symmetry=True
	for j in range(d,2*d,1):
		if a[i] != a[j]:
			symmetry=False
			break
		i-=1
	if symmetry:
		small=d
	else:
		break
		
	if d%2:
		break
	d//=2

print(small)



n, m = tuple(map(int, str.split(input())))
a = list([input() for _ in range(n)])
while n % 2 == 0 and all([a[i] == a[-i - 1] for i in range(n // 2)]):

    n //= 2
    a = a[:n]

print(n)


def readln(): return tuple(map(int, input().split()))

n, m = readln()
a = [readln() for _ in range(n)]
ans = n
while ans % 2 == 0:
    p1 = a[:ans // 2]
    p2 = a[ans // 2:]
    p2.reverse()
    if p1 != p2:
        break
    a = p1
    ans //= 2
print(ans)

n,m = map(int,input().split())
matrix = []
for i in range(n):
    arr = list(map(int,input().split()))
    matrix.append(arr)
while n and n&1==0:
    t = n//2
    flag = True
    for i in range(n):
        if matrix[i] != matrix[n-1-i]:
            flag = False
    if flag == False:
        break
    else:n >>= 1
print(n)

__author__ = 'Lipen'


def main():
	n, m = map(int, input().split())
	a = []
	for _ in range(n):
		a.append(input())

	while n%2==0:
		if a[:n//2] != a[:n//2-1:-1]:
			break
		n //= 2
		a = a[:n]

	print(n)

main()

n, m = map(int, input().split())
if n & 1: print(n)
else:
    k, t = n // 2, [int(input()[:: 2], 2) for i in range(n)]
    while True:
        if t[: k] != t[k: 2 * k][:: -1]:
            print(2 * k)
            break
        elif k & 1:
            print(k)
            break
        k //= 2

#-------------------------------------------------------------------------------
# Name:        module1
# Purpose:
#
# Author:      Administrator
#
# Created:     03/05/2014
# Copyright:   (c) Administrator 2014
# Licence:     <your licence>
#-------------------------------------------------------------------------------

n, m = map(int, input().split())
if n & 1 :
    print(n)
else:
    k, t = n // 2, [int(input()[::2], 2) for i in range(n)]
    while True:
        if t[:k] != t[k:2*k][::-1]:
            print(2 * k)
            break
        elif k & 1:
            print(k)
            break
        k //= 2

n, m = map(int, input().split())
a = [int(input()[::2], 2) for i in range(n)]
if n & 1:
    print(n)
else:
    k = n // 2
    while True:
        if a[:k] != a[k:k*2][::-1]:
            print(k * 2)
            break
        elif k & 1:
            print(k)
            break
        k //= 2

import sys

def mirror(row, matrix):
    if row % 2:
        return row
    else:
        for i in range(row // 2):
            if matrix[i] != matrix[row - 1 - i]:
                return row
        return mirror(row // 2, matrix)

def __starting_point():
    n, m = list(map(int, sys.stdin.readline().split()))
    matrix = [list(map(int, i.split())) for i in sys.stdin.readlines()]
    print(mirror(n, matrix))


__starting_point()

(a,b)=map(int, input().split())
if a%2==0:
    s=[0]*a
    for i in range(a):
        s[i]=[0]*b
        s[i]=list(map(int, input().split()))
    while s[:a//2]==s[:a//2-1:-1] and len(s)>1:
        a=a//2
        s=s[:a]
else:
    for i in range(a):
        n=input()
print(a)      

n, m = map(int, input().split())
mat = [input() for _ in range(n)]
ans = n

while ans > 1 and ans % 2 == 0:
    if mat[:ans] == list(reversed(mat[:ans])):
        ans //= 2
    else:
        break
    if ans == 1:
        if len(set(mat)) > 1:
            ans = 2
        break

print(ans)