Let $k$ be the greatest such integer. We will show that $k=3$ when $n$ is odd and $k=6$ when $n$ is even.

We will say that a number $p$ is nice if $p$ is a prime number of the form $2 \bmod 3$ which does not divide $N$.

Note first that if $3 \mid p+1$ for every nice number $p$ and so $k$ is a multiple of 3.
If $n$ is odd, then $p=2$ is nice, so we must have $k \mid 3$. From the previous paragraph we get that $k=3$.

If $n$ is even, then $p=2$ is not nice, therefore every nice $p$ is of the form $5 \bmod 6$. So in this case $6 \mid p+1$ for every nice number $p$.

It remains to show that (if $n$ is even then)
(i) There is a nice $p$ such that $4 \nmid p+1$.
(ii) There is a nice $p$ such that $9 \nmid p+1$.
(iii) There is a nice $p$ such that for every prime $q \neq 2,3$ we have that $q \nmid p+1$.

For (i), by Dirichlet's theorem on arithmetic progressions, there are infinitely many primes of the form $p \equiv 5 \bmod 12$. Any one of them which is larger than $n$ will do.

For (ii), by Dirichlet's theorem on arithmetic progressions, there are infinitely many primes of the form $p \equiv 2 \bmod 9$. Any one of them which is larger than $n$ will do.

For (iii), by Dirichlet's theorem on arithmetic progressions, there are infinitely many primes of the form $p \equiv 2 \bmod 3 q$. Any one of them which is larger than $n$ will do.

Remark. In the proposal, the statement of Dirichlet's theorem on Arithmetic Progressions was given as known. Even though this makes the problem fairer we omitted it because we feel that it also makes it easier.