I think you’re splitting your circles into cases wrong. Say you have circles with centers c_1,c_2 and radii r_1,r_2 (wlog assume that r_1 \ge r_2), then you want to split circles with into the cases

Completely disjoint, c_1c_2 > r_1+r_2

One circle inside the other, not disjoint and c_1c_2 < r_1  r_2

Intersecting, not disjoint and not inside
All these cases have the same maximum distance d_\text{max} = r_1 + r_2 + c_1c_2 but different minimum distances
d_\text{min} =
\begin{cases}
c_1c_2  r_1  r_2 & \text{if disjoint} \\
r_1  r_2  c_1c_2 & \text{if nested} \\
0 & \text{if intersecting} \\
\end{cases}
You can probably see why those distances are correct if you just draw the circles. If you don’t I could post some images.
When you have computed all [d_\text{min},d_\text{max}] intervals you can for the small case do the O(Q N^2) approach just by checking all intervals against the given d. To get the large case as well you need to be a bit more clever and use sorting and binary search to speed up things to time complexity O(N^2 \log{N} + Q \log{N}).