HMMT 2020 T10

Let $n$ be a fixed positive integer, and choose $n$ positive integers $a_{1}, \ldots, a_{n}$. Given a permutation $\pi$ on the first $n$ positive integers, let $S_{\pi}=\left\{i \left\lvert \frac{a_{i}}{\pi(i)}\right.\right.$ is an integer $\}$. Let $N$ denote the number of distinct sets $S_{\pi}$ as $\pi$ ranges over all such permutations. Determine, in terms of $n$, the maximum value of $N$ over all possible values of $a_{1}, \ldots, a_{n}$.