What if I drop the 1?

So we have $n^2 - 1 \equiv 0 \pmod{360}$ . By factoring $360$ into product of coprime positive integers, we have $360 = 5 \times 8 \times 9$ .

Thus $n^2 \equiv 1 \pmod{5}, n^2 \equiv 1 \pmod{8}, n^2 \equiv 1 \pmod{9}$ .

By quotient remainder theorem, it's easy to see that for $n^2 \equiv 1 \pmod 5$ yields $n \equiv \pm 1 \pmod 5$ . Similarly, for the other quadratic congruences, we can obtain $n \equiv \pm 1, \pm 3 \pmod 8$ and $n \equiv \pm 1 \pmod 9$ .

So there's $2, 4, 2$ possible remainders of $n$ when divided by $5, 8, 9$ respectively. By Chinese Remainder Theorem and by rule of product, the total number of solutions when $k$ is restricted in the interval $[0,360]$ is simply $2\times 4\times 2=\boxed{16}$ .

The answer is 16.