CL-MO 2016

The giraffe is a chess piece that moves $4$ squares in one direction and then a box in a perpendicular direction. What is the smallest value of $n$ such that the giraffe that starts from a corner on an $n \times n$ board can visit all the squares of said board?