k-совершенные числа
Известно, что число называется совершенным, если оно равно сумме всех своих положительных делителей, кроме его самого. Например, первое совершенное число – 6 = 1 + 2 + 3. Теперь сформулируем это более строго, рассмотрим функцию:
Число является совершенным тогда и только тогда, когда σ(n) – n = 0.
Назовем число k-совершенным, если |σ(n) – n| = k. Таким образом 2-совершенными числами будут, например, 3 и 10. Ваша задача найти количество k-совершенных чисел на отрезке [l, r].
Входные данные
В первой строке входного файла задано количество тестов t (1 ≤ t ≤ 100000). Каждый тест состоит из одной строки, содержащей три целых числа l, r и k, разделенных одним пробелом (1 ≤ l ≤ r ≤ 10^6, 0 ≤ k ≤ 10^9).
Выходные данные
Для каждого теста выведите строку, содержащую количество k-совершенных чисел на отрезке [l, r].