def A(n):
	verbose=0
	l=0
	if n==1:
		return 1
	elif n<1:
		return 0
	elif n%2==1:
		f=[-1 for x in range(n*n)]
		d=[0 for x in range(n*n+1)]
		dd=[0 for x in range(n*n+1)]
		way=[0 for x in range(n*n)]
		st=1
		d[0]=2
		f[1]=0
		f[n*n-1]=n
		f[n*n-1]=0
		d[1]=2
		way[0]=2
		dd[0]=2
		dd[1]=2
		i=1
		while st>=1:
			jjj=i
			if d[st]==1:
				if dd[st+1]==0 and i>=n and f[i-n]<0 and f[n*n-1-(i-n)]<0:
					st=st+1
					d[st]=1
					dd[st]=1
					f.pop(i-n)
					f.insert(i-n,i)
					f.pop(n*n-1-i+n)
					f.insert(n*n-1-i+n,i)
					i=i-n
				elif dd[st+1]!=4 and dd[st+1]!=2 and i%n<n-1 and f[i+1]<0 and f[n*n-1-(i+1)]<0:
					st=st+1
					d[st]=2
					dd[st]=2
					f.pop(i+1)
					f.insert(i+1,i)
					f.pop(n*n-2-i)
					f.insert(n*n-2-i,i)
					i=i+1
				elif dd[st+1]!=4 and i%n>0 and f[i-1]<0 and f[n*n-1-(i-1)]<0:
					st=st+1
					d[st]=4
					dd[st]=4
					f.pop(i-1)
					f.insert(i-1,i)
					f.pop(n*n-i)
					f.insert(n*n-i,i)
					i=i-1
				else:
					d[st]=0
			elif d[st]==2:
				if dd[st+1]==0 and i%n<n-1 and f[i+1]<0 and f[n*n-1-(i+1)]<0:
					st=st+1
					d[st]=2
					dd[st]=2
					f.pop(i+1)
					f.insert(i+1,i)
					f.pop(n*n-2-i)
					f.insert(n*n-2-i,i)
					i=i+1
				elif dd[st+1]%2!=1 and i<n*(n-1) and f[i+n]<0 and f[n*n-1-(i+n)]<0:
					st=st+1
					d[st]=3
					dd[st]=3
					f.pop(i+n)
					f.insert(i+n,i)
					f.pop(n*n-1-i-n)
					f.insert(n*n-1-i-n,i)
					i=i+n
				elif dd[st+1]!=1 and i>=n and f[i-n]<0 and f[n*n-1-(i-n)]<0:
					st=st+1
					d[st]=1
					dd[st]=1
					f.pop(i-n)
					f.insert(i-n,i)
					f.pop(n*n-1-i+n)
					f.insert(n*n-1-i+n,i)
					i=i-n
				else:
					d[st]=0
			elif d[st]==3:
				if dd[st+1]==0 and i<n*(n-1) and f[i+n]<0 and f[n*n-1-(i+n)]<0:
					st=st+1
					d[st]=3
					dd[st]=3
					f.pop(i+n)
					f.insert(i+n,i)
					f.pop(n*n-1-i-n)
					f.insert(n*n-1-i-n,i)
					i=i+n
				elif dd[st+1]!=4 and dd[st+1]!=2 and i%n>0 and f[i-1]<0 and f[n*n-1-(i-1)]<0:
					st=st+1
					d[st]=4
					dd[st]=4
					f.pop(i-1)
					f.insert(i-1,i)
					f.pop(n*n-i)
					f.insert(n*n-i,i)
					i=i-1
				elif dd[st+1]!=2 and i%n<n-1 and f[i+1]<0 and f[n*n-1-(i+1)]<0:
					st=st+1
					d[st]=2
					dd[st]=2
					f.pop(i+1)
					f.insert(i+1,i)
					f.pop(n*n-2-i)
					f.insert(n*n-2-i,i)
					i=i+1
				else:
					d[st]=0
			elif d[st]==4:
				if dd[st+1]==0 and i%n>0 and f[i-1]<0 and f[n*n-1-(i-1)]<0:
					st=st+1
					d[st]=4
					dd[st]=4
					f.pop(i-1)
					f.insert(i-1,i)
					f.pop(n*n-i)
					f.insert(n*n-i,i)
					i=i-1
				elif dd[st+1]%2!=1 and i>=n and f[i-n]<0 and f[n*n-1-(i-n)]<0:
					st=st+1
					d[st]=1
					dd[st]=1
					f.pop(i-n)
					f.insert(i-n,i)
					f.pop(n*n-1-i+n)
					f.insert(n*n-1-i+n,i)
					i=i-n
				elif dd[st+1]!=3 and i<n*(n-1) and f[i+n]<0 and f[n*n-1-(i+n)]<0:
					st=st+1
					d[st]=3
					dd[st]=3
					f.pop(i+n)
					f.insert(i+n,i)
					f.pop(n*n-1-i-n)
					f.insert(n*n-1-i-n,i)
					i=i+n
				else:
					d[st]=0
			way.pop(jjj)
			way.insert(jjj,d[st])
			if verbose==1:
				print(st,i)
				kk=1
				ww="→"
				while kk<n*n:
					if kk%n==0:
						ww=ww+"\n"
					if way[kk]==2:
						ww=ww+"→"
					elif way[kk]==3:
						ww=ww+"↓"
					elif way[kk]==4:
						ww=ww+"←"
					elif way[kk]==1:
						ww=ww+"↑"
					else:
						ww=ww+" "
					kk=kk+1
				print(ww)
			if i==(n*n-1)/2:
				if st==(n*n-1)/2:
					l=l+1
					print(n,"   ",l)
					kk=1
					ww="→"
					while kk<n*n-1:
						if kk%n==0:
							ww=ww+"\n"
						if way[kk]==2:
							ww=ww+"→"
						elif way[kk]==3:
							ww=ww+"↓"
						elif way[kk]==4:
							ww=ww+"←"
						elif way[kk]==1 or way[f[n*n-kk-1]]==1:
							ww=ww+"↑"
						elif way[f[n*n-kk-1]]==2:
							ww=ww+"→"
						elif way[f[n*n-kk-1]]==3:
							ww=ww+"↓"
						elif way[f[n*n-kk-1]]==4:
							ww=ww+"←"
						else:
							ww=ww+" "
						kk=kk+1
					ww=ww+" "
					print(ww)
					way.pop(i)
					way.insert(i,0)
					jj=i
					i=f[i]*1
					f.pop(jj)
					f.insert(jj,-1)
					f.pop(n*n-1-jj)
					f.insert(n*n-1-jj,-1)
					d[st]=0
					st=st-1
					d[st]=0
			if d[st]==0:
				way.pop(i)
				way.insert(i,0)
				dd[st+1]=0
				jj=i
				i=f[i]*1
				f.pop(jj)
				f.insert(jj,-1)
				f.pop(n*n-1-jj)
				f.insert(n*n-1-jj,-1)
				st=st-1
	elif n%2==0:
		bo=int(n*n/2)
		f=[-1 for x in range(n*n)]
		d=[0 for x in range(bo+1)]
		dd=[0 for x in range(bo+1)]
		way=[0 for x in range(n*n)]
		st=1
		d[0]=2
		f[1]=0
		d[1]=2
		dd[0]=2
		dd[1]=2
		i=1
		down=0
		while st>=0:
			if st==0:
				down=1
			jjj=i
			if d[st]==1:
				if dd[st+1]==0 and i>=n and f[i-n]<0:
					st=st+1
					d[st]=1
					dd[st]=1
					f.pop(i-n)
					f.insert(i-n,i)
					i=i-n
				elif dd[st+1]!=4 and dd[st+1]!=2 and i%n<n-1 and f[i+1]<0:
					st=st+1
					d[st]=2
					dd[st]=2
					f.pop(i+1)
					f.insert(i+1,i)
					i=i+1
				elif dd[st+1]!=4 and i%n>0 and f[i-1]<0:
					st=st+1
					d[st]=4
					dd[st]=4
					f.pop(i-1)
					f.insert(i-1,i)
					i=i-1
				else:
					d[st]=0
			elif d[st]==2:
				if dd[st+1]==0 and i%n<n-1 and f[i+1]<0:
					st=st+1
					d[st]=2
					dd[st]=2
					f.pop(i+1)
					f.insert(i+1,i)
					i=i+1
				elif dd[st+1]%2!=1 and i<bo-n and f[i+n]<0:
					st=st+1
					d[st]=3
					dd[st]=3
					f.pop(i+n)
					f.insert(i+n,i)
					i=i+n
				elif dd[st+1]!=1 and i>=n and f[i-n]<0:
					st=st+1
					d[st]=1
					dd[st]=1
					f.pop(i-n)
					f.insert(i-n,i)
					i=i-n
				else:
					d[st]=0
			elif d[st]==3:
				if dd[st+1]==0 and i<bo-n and f[i+n]<0:
					st=st+1
					d[st]=3
					dd[st]=3
					f.pop(i+n)
					f.insert(i+n,i)
					i=i+n
				elif dd[st+1]!=4 and dd[st+1]!=2 and i%n>0 and f[i-1]<0:
					st=st+1
					d[st]=4
					dd[st]=4
					f.pop(i-1)
					f.insert(i-1,i)
					i=i-1
				elif dd[st+1]!=2 and i%n<n-1 and f[i+1]<0:
					st=st+1
					d[st]=2
					dd[st]=2
					f.pop(i+1)
					f.insert(i+1,i)
					i=i+1
				else:
					d[st]=0
			elif d[st]==4:
				if dd[st+1]==0 and i%n>0 and f[i-1]<0:
					st=st+1
					d[st]=4
					dd[st]=4
					f.pop(i-1)
					f.insert(i-1,i)
					i=i-1
				elif dd[st+1]%2!=1 and i>=n and f[i-n]<0:
					st=st+1
					d[st]=1
					dd[st]=1
					f.pop(i-n)
					f.insert(i-n,i)
					i=i-n
				elif dd[st+1]!=3 and i<bo-n and f[i+n]<0:
					st=st+1
					d[st]=3
					dd[st]=3
					f.pop(i+n)
					f.insert(i+n,i)
					i=i+n
				else:
					d[st]=0
			way.pop(jjj)
			way.insert(jjj,d[st])
			if verbose==1:
				print(st,i)
				si=1
				if si==1:
					kk=1
					if down==0:
						ww="→"
					else:
						ww="↓"
					while kk<bo:
						if kk%n==0:
							ww=ww+"\n"
						if way[kk]==2:
							ww=ww+"→"
						elif way[kk]==3:
							ww=ww+"↓"
						elif way[kk]==4:
							ww=ww+"←"
						elif way[kk]==1:
							ww=ww+"↑"
						else:
							ww=ww+" "
						kk=kk+1
				print(ww)
			if st==bo-1:
				if i>=bo-n:
					l=l+1
					print(n,"   ",l)
					kk=1
					if down==0:
						way[0]=2
					else:
						way[0]=3
					way[i]=3
					ww=""
					while kk<n*n:
						if kk%n==0:
							ww=ww+"\n"
						if down==0:
							if way[kk]==2 or way[f[(n-1-int(kk/n))*n+kk%n]]==4:
								ww=ww+"→"
							elif way[kk]==3 or way[f[(n-1-int(kk/n))*n+kk%n]]==3:
								ww=ww+"↓"
							elif way[kk]==4 or way[f[(n-1-int(kk/n))*n+kk%n]]==2:
								ww=ww+"←"
							elif way[kk]==1 or way[f[(n-1-int(kk/n))*n+kk%n]]==1:
								ww=ww+"↑"
							else:
								ww=ww+" "
						else:
							kl=(kk%n)*n+int(kk/n)
							ll=(n-int(kl/n)-1)*n+kl%n
							if way[kl]==3 or way[f[ll]]==3:
								ww=ww+"→"
							elif way[kl]==2 or way[f[ll]]==4:
								ww=ww+"↓"
							elif way[kl]==1 or way[f[ll]]==1:
								ww=ww+"←"
							elif way[kl]==4 or way[f[ll]]==2:
								ww=ww+"↑"
							else:
								ww=ww+" "
						kk=kk+1
					ww="→"+ww
					print(ww)
				way.pop(i)
				way.insert(i,0)
				jj=i
				i=f[i]*1
				f.pop(jj)
				f.insert(jj,-1)
				d[st]=0
				st=st-1
				d[st]=0
			if d[st]==0:
				way.pop(i)
				way.insert(i,0)
				dd[st+1]=0
				jj=i
				i=f[i]*1
				f.pop(jj)
				f.insert(jj,-1)
				st=st-1
	return l