The answer is 91; in general, for a $1 \times n^2$ board, the minimum possible value of $N$ is $2n-1$.

Construction: Cut the $1 \times n^2$ strip into $2n-1$ pieces of lengths $n, 1, n, \dots, 1, 1$. Use the first piece of length $n$ to form the first row, and so on, forming the lower $(n-1) \times n$ array, and then use all the pieces of length $1$ to form the last row. (Remark: this is not the only construction method.)

Estimate: Since the requirement of the problem only concerns the remainder of the labels modulo $n$, the following discussion is all carried out under congruence mod $n$.

Consider the vertex set $V = \{0, 1, \dots, n-1\}$, and connect edges according to the following rule: for each piece of wood sawed out, if the labels of its left and right ends are $a$ and $b$ respectively, then connect vertex $a$ and vertex $b+1$ by an edge (loops and multiple edges are allowed). Note that the total number of edges equals the number of pieces sawed out, so we only need to prove that, under the conditions of the problem, the resulting edge set $E$ must have at least $2n-1$ edges.

Note that the resulting graph $G = (V, E)$ has the following properties:

1. Since the pieces of wood can be joined together to form the sequence from 1 to $n^2$, $G$ has an Eulerian circuit.

2. Since the labels of the squares in column $k$ of the array are $k, k+1, \dots, k+n-1$ in order, all the pieces of wood in column $k$ of the array correspond to a cycle $\gamma_k$, and $\gamma_k$ must contain vertex $k$ (because the label of the leftmost square of the leftmost piece is $k$).

From 1., $G$ is connected. Moreover, since any two $\gamma_k$ share no common edge (because a piece of wood can only appear in one column), if we remove one edge from each $\gamma_k$, the resulting new graph $G' = (V, E')$ remains connected. This implies $|E'| \ge |V| - 1 = n - 1$, and hence $|E| = |E'| + n \ge 2n - 1$. This completes the proof.