Let $A=(a_{ij})$ be the $n \times n$ matrix, where $a_{ij}$ is the remainder of the division of $i^j + j^i$ by $3$ for $i,j=1,2,\ldots,n$. Find the greatest $n$ for which $\det A \neq 0$.

Let's think step by step and output the final answer within \boxed{}.
user