Посчитаем $\text{rad}(n)$ и простые множители в разложении $\text{rad}(n)$ для $n$ до $10^6$ с помощью линейного решета Эратосфена. Тогда $\text{rad}(abc) = m$ разделим на все простые множители, входящие в $\text{rad}(a)$ и $\text{rad}(c)$, получим \it{обязательные} множители в $b$, которое обозначим за $r$.

Здесь важно отметить, что не гарантируется корректность $m$, то есть оно может содержать либо простое число, большее, чем $c$, либо делиться на квадрат простого, либо не делиться на нужные простые числа вообще. Также отдельным случаем можно было рассмотреть $m=1$, потому что в некоторых реализациях это могло иметь значение.

Теперь задача сводится к тому, чтобы найти такие числа $\lambda$, которые представимы в виде произведения простых множителей из $m$, возведенных в некоторые (неотрицательные) степени. Если простые множители обозначить за $p_i$, то $\lambda$ имеют такой вид:
 $$\lambda = p_1^{\alpha_1} \cdot p_2^{\alpha_2}\cdot \ldots \cdot p_k^{\alpha_k} $$

При этом степени вхождения простых чисел, которые делят число $r$ должны быть не менее $1$.

Как построить все такие числа $\lambda$? Для начала можно заметить, что количество \textbf{различных} простых в числе $abc$ не больше $14$. (Доказательство этого факта оставим как упражнение читателю).

Тогда можно построить рекурсию (что также можно назвать $\text{dfs}$ по числам), в которой мы будем домножать число на очередное простое и проверять, подходит ли текущее число в рекурсии под ограничения $a < \lambda < c$. Так как нам неважно в каком порядке будут рассматриваться простые множители, ведь $x \cdot y = y \cdot x$, можно перебирать в порядке неубывания.

Можно показать, что такая рекурсия будет работать примерно за $O(\sqrt{c}\log c)$. Доказательство этого факта не требовалось. Если вы дошли до факта, что различных простых в числе не больше $14$, то можно было запустить рекурсию для максимального теста --- $a = 1, c = 10^6$ и количество простых $14$ (Естественно, это не сам \it{максимальный} тест, но что-то похожее, что поможет вам оценить количество операций). В результате получим, что в этом случае производится всего $\approx 54 \cdot 10^3$ операций, а для $t = 10^3$, количество операций будет $\approx 5 \cdot 10^7$. На языке $\text{C++}$ укладывается в ограничения по времени.

Время работы этого решения $O(t\sqrt{c}\log c)$.