ELMO SL 2018 N4

Say a positive integer $n>1$ is $d$ -coverable if for each non-empty subset $S\subseteq \{0, 1, \ldots, n-1\}$ , there exists a polynomial $P$ with integer coefficients and degree at most $d$ such that $S$ is exactly the set of residues modulo $n$ that $P$ attains as it ranges over the integers. For each $n$ , find the smallest $d$ such that $n$ is $d$ -coverable, or prove no such $d$ exists.

Proposed by Carl Schildkraut