k-досконалі числа#3233
Відомо, що число називається досконалим, якщо воно дорівнює сумі всіх своїх додатних дільників, окрім самого себе. Наприклад, перше досконале число — це 6 = 1 + 2 + 3. Тепер сформулюємо це більш строго. Розглянемо функцію:
Число є досконалим тоді й лише тоді, коли \sigma(n) - n = 0.
Число називається -досконалим, якщо |\sigma(n) - n| = k. Таким чином, наприклад, -досконалими числами є і . Ваше завдання — знайти кількість -досконалих чисел на відрізку [l, r].
У першому рядку вхідного файлу записано число тестів (1 \leq t \leq 100\,000). Кожний тест складається з одного рядка, що містить три цілі числа , і , розділених пробілами (1 \leq l \leq r \leq 10^6, 0 \leq k \leq 10^9).
Для кожного тесту виведіть рядок, що містить кількість -досконалих чисел на відрізку [l, r].
Приклад 1