It's n=8. Disprove earlier cases then use the fact that 2 is a quadratic residue mod primes 8k+1 and 8k+7. Also see that -2 is a quadratic residue mod primes which are 8k+3. Suppose that X^4 =-4 mod p then (X^2+2x+2)(x^2-2x+2) = 0 mod p let (X+1)^2=-1 mod p This exists modulo primes 8k+5 so we have shown n<=8. For n=5, check modulo 11. For n=6 check modulo 13. For n=7 I am not sure if there is a nice method but it breaks modulo 43.

For $n=7$ modulo $29$ also works. Indeed, if $x^7 \equiv 16$, then by Fermat $1\equiv x^{28} \equiv 16^4 \equiv 25 \pmod {29}$, contradiction.