　以下を $4$ 頂点とする正方形に平行移動のみで一致させられる格子正方形を $S(x,y)$ で表す．
$$(x,0),　(0,y),　(x+y,x),　(y,x+y)$$
ただし，$x\geq0,y\gt 0$ とする．また，格子正方形の**レベル**を以下で定義する．

- $x=0$ のとき，$S(x,y)$ のレベルを $y$ で定める．
- $x\neq 0$ のとき，$S(x,y)$ のレベルを $x+y-1$ で定める．

　このとき，レベル $L$ の格子正方形に含まれる格子正方形のレベルは $L$ 未満であることが容易に確認できる．特に，レベル $L$ の格子正方形にレベル $L-1$ の格子正方形が含まれるのは，以下のようなケースに限られる．

- $S(0,y)$ に含まれる $S(0,y-1)$ または $S(k,y-k)~(k=1,2,\ldots,n-1)$
- $x=1$ または $y=1$ (もう一方は $2$ 以上) について $S(x,y)$ に含まれる $S(0,x+y-2)$
- $S(2,2)$ に含まれる $S(0,2)$

　よって $n$ の最大値は $N$ であり，$M_1=1, M_2=5$ および以下の漸化式の成立が分かる.
$$M_{N+2}=4M_{N+1}+2M_N$$
ただし，$N=2$ のときのみ $M_N$ の係数が $3$ となる．$M_N$ が $2$ で割れる最大の回数を $a_N$ とすれば，
$$a_{4k+1}\geq 2k+1,\quad a_{4k+2}=2k-1,\quad a_{4k+3}=2k+1,\quad a_{4k+4}=2k\quad (k=1,2,\ldots)$$
が成立する．したがって $N=\bf{24694}$ のときに $a_N=12345$ となり，これが求める最大のものである．
公式解説
https://onlinemathcontest.com/contests/omc083/editorial/2992
　$N$ を正整数とします. $xy$ 座標平面上に正方形 $S_1, S_2, \ldots, S_n$ があり, 以下の条件を満たしています.
- 全ての正方形の頂点は格子点である.
- $S_1$ は $(0,0), (0,N), (N,0), (N,N)$ を頂点とする.
- 任意の $1\leq k \leq n-1$ について, $S_{k+1}$ は $S_k$ の辺上を含む内部にあり, かつ一致しない.

このような $(S_1, S_2, \ldots, S_n)$ のうち, $n$ が最大値をとるものの個数を $M_N$ で表します.\
　$M_N$ が $2$ で割り切れる回数がちょうど $12345$ 回であるような最大の $N$ を求めてください.