Try $q(x) = (x^2+1)^3$ with $n = 6$.  The following $6$ linearly independent polynomials $p(x)$ qualify:
$$ 4 x - 3, x^2, 4 x^3 - 1, x^4 + 1, x^6 - 6, 2 x^7 + 6 x^5 - 1 $$