The obvious solution, if we did not care about the bound, is something like $N = 22!$. Then, $N + k$ is divisible by $k$ for $k = 2, \dots, 22$. However, $22!$ is far too large.

Instead, we take $N$ to have several small prime factors in order that $N + k$ has small factors for most values of $k = 2, \dots, 22$, and we then tweak $N$ to take care of missing factors. We want a small $N$ so we have to try to be efficient: small factors, and factors that handle several values of $k$, are best.

It makes sense to start with taking $N$ to be a multiple of both $2$ and $3$, since these factors are small, and together they handle all values of $k$ except $k \in \{5, 7, 11, 13, 17, 19\}$.

We next assume that $N \equiv 3 \pmod{5}$ since this is more efficient than assuming that $N$ is a multiple of $5$: the former handles two of the remaining values of $k$ (namely $k=7$ and $k=17$), whereas the latter handles only $k=5$. This leaves $k \in \{5, 11, 13, 19\}$ to be handled. For a similar reason, we assume that $N \equiv 2 \pmod{7}$ in order to handle $k=5$ and $k=19$, leaving only $k \in \{11, 13\}$. Finally, we assume that $N$ is a multiple of $11$ and of $13$ to handle these two values of $k$.

Thus, $N$ is a multiple of $n := 2 \cdot 3 \cdot 11 \cdot 13 = 858$. Note that $n$ equals $3 \bmod 5$, as desired. Thus, we need $N$ to differ from $n$ by a multiple of $5n$. Now, $n \equiv 4 \pmod{7}$, and $5n \equiv -1 \pmod{7}$, so $N = 11n$ is what we need.

Clearly, $N$ has at least four digits, so it remains to check that $N = 2 \cdot 3 \cdot 11^2 \cdot 13$ is at most $9999 - 22$. In fact, it is easier to compare $N$ with $A = 9900$. It is clear that $N/66 = 11 \cdot 13 = 143$, while $A/66 = 150$, so we are done.