Start by placing number $1$ anywhere on an infinite square grid. Now place numbers $2, 3, 4, \ldots, K$ in order. A number $k$ can be placed if the following rules hold:
- It must be adjacent (horizontally or vertically) to the previous number $k-1$.
- It must have at least one neighbour (horizontally or vertically) number $m$ already placed such that $k+m$ is prime. Note that $m$ can be $k-1$.
What is the largest number $K$ that you can place? You can use a computer if you want.