USAJMO 2010 Question 1

Let $P(n)$ be the number of permutations $(a_1,\ldots,a_n)$ of $1,2,\ldots,n$ such that $ka_k$ is a perfect square for every $1\le k\le n$. Find, with proof, the smallest $n$ for which $2010\mid P(n)$.

Proposed by Andy Niedermier (credit in the supplied notes).