Can you solve it if all squares have the same number of digits?

In the general case in which squares may have a different number of digits, group them by their number of digits, and use the previous algorithm for each group.

Suppose all the squares have the same number of digits. For example, let's say 2 digits.

The numbers that have 2-digit squares are in the interval [4, 9].

Now, given a query q, you can easily see where the digit q belongs, because there are 6 squares with 2-digits each (12 digits).

16|25|36|49|64|81

Find the block (or bucket) where q falls into with a simple division.

You can use this strategy in the general case, just keep track of all the intervals that contain 1-digit squares, 2-digit squares, 3-digit squares, 4-digit squares ... etc

thanks for the help guys!, im guessing you have to precompute the frequency of every digit number, so thats what i did, i tried running the precomputation algo in my machine, it took about 2,5 seconds to generate, so i got worried and run it offline, then just hardcode it into the program, and got AC 1 ms :D

but, because im curious, i just use the precomputation algo on the start of the program, and submit it again, and i got AC ~400 ms ._., so i guess my machine is just really slow :(

for the future, here is how i solve the problem: https://ideone.com/S3OBbq (commented out lines is the wy i precompute)