Below is the result of an experiment for \(n=20\) and completely random input:

11221202210202021111
02010120101010102020
10101012010101010101
01010101201010101010
20101010120101010101
12010101012010101010
01201010101201010101
02010101010120101010
01201010101012010101
20120101010101201010
12012010101010120101
10101201010101012010
21010120101010101201
20101012010101010120
12010101201010101012
20101010120101010101
01010101012010101010
10101010101201010101
12010101010120101010
01201010101012010101

We can see that, for somewhat large \(i\) and \(j\), the same value appears again and again from upper-left to lower-right.

Actually, we can show that \(a_{4, 4} = a_{5, 5}\) always holds by case analysis or brute force. Thus, by naively computing just the four topmost rows and four leftmost columns, we can solve the problem in \(O(N)\) time.