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].