eolymp
bolt
Try our new interface for solving problems
Məsələlər

k-совершенные числа

k-совершенные числа

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Известно, что число называется совершенным, если оно равно сумме всех своих положительных делителей, кроме его самого. Например, первое совершенное число – 6 = 1 + 2 + 3. Теперь сформулируем это более строго, рассмотрим функцию:

Число является совершенным тогда и только тогда, когда σ(n) – n = 0.

Назовем число k-совершенным, если |σ(n) – n| = k. Таким образом 2-совершенными числами будут, например, 3 и 10. Ваша задача найти количество k-совершенных чисел на отрезке [l, r].

Giriş verilənləri

В первой строке входного файла задано количество тестов t (1t100000). Каждый тест состоит из одной строки, содержащей три целых числа l, r и k, разделенных одним пробелом (1lr10^6, 0k10^9).

Çıxış verilənləri

Для каждого теста выведите строку, содержащую количество k-совершенных чисел на отрезке [l, r].

Nümunə

Giriş verilənləri #1
3
1 10 2
1 10 0
36 100 4
Çıxış verilənləri #1
2
1
3
Müəllif Евгений Служаев