Every positive integer $k$ can be expressed in the form $2^a5^bc$, where $a,b,c$ are nonnegative integers and $gcd(c,10)=1$. By Euler's Theorem, $c \mid 10^{\varphi(c)} - 1$. Also, $2^a5^b \mid 10^{max\{a, b\}}$. If we let $n = (10^{\varphi(c)} - 1)10^{max\{a, b\}}$, then $k \mid n$. Since $Q(10^{2m} - 2 \cdot 10^m + 1) = Q(10^m - 2) + 1 = Q(10^m - 1)$ for all nonnegative integers $m$, $Q(n) = Q(n^2)$. Therefore, there exists a multiple $n$ of $k$ such that $Q(n) = Q(n^2)$.

Every number of the form $10^i-1$ satisfies $Q(n)=Q(n^2)$ and since there are finitely many residue classes mod $k$, there are $i<j$ with $10^i-1\equiv 10^j-1\mod k$. It's easy to see that the number $10^j-10^i$ satisfies the desired condition.