How many integer values of $k$, with $1 \leq k \leq 70$, are such that $x^{k}-1 \equiv 0 \pmod{71}$ has at least $\sqrt{k}$ solutions?

Let's think step by step and output the final answer within \boxed{}.
user