It is easy to prove that for any number n and bases > sqrt(n) there will be no representation where the number will contain 0 at its second least significant digit. So it is enough to check for bases ≤ sqrt(n).
As there are 106 test cases, you have to precalculate the results to avoid TLE.
Time complexity: O(n × sqrt(n) + Q)
where Q is the number of queries and n is the highest possible number in the query.