Suppose $a$ is a square-free integer and $\left(\frac{a}{p}\right)=1$ for the primes $p\leq k$. I'll call $a$ a quasi-square of order $k$. What I am interested in is the maximum value of $k$ in terms of $a$. For instance if $a$ is a prime which is $1$ mod $4$ then by quadratic reciprocity, we are really asking about the least non-residue mod $a$. So on the GRH we have $k=O((\log a)^2)$. But if we think about these symbols as coin flips, then I would suspect that after about $\log_2 a$ primes we should see a $-1$. So, since the $n$'th prime is about $n\log n$ one might guess that $k$ should be not much larger than $(\log_2 a)(\log\log a)$. Is this reasonable? Is there a well-known conjecture which suggests this? Does it hold on average?

Edit: As further justification, if we look at all $N\leq a\leq 2N$ then checking that $\left(\frac{a}{p}\right)=1$ rules out half of the integers in this range. So we should be run out of integers after about $\log_2 N$ primes. Of course the squares will remain, but that should be it.