Известно, что число называется совершенным, если оно равно сумме всех своих положительных делителей, кроме его самого. Например, первое совершенное число -- \textbf{6 = 1 + 2 + 3}. Теперь сформулируем это более строго, рассмотрим функцию: \includegraphics{https://static.e-olymp.com/content/9a/9a0eb405326f047983fb4f3ba4d68cc201bca30f.jpg} Число является совершенным тогда и только тогда, когда \textbf{σ(n) -- n = 0}. Назовем число \textbf{k}-совершенным, если \textbf{|σ(n) -- n| = k}. Таким образом \textbf{2}-совершенными числами будут, например, \textbf{3} и \textbf{10}. Ваша задача найти количество \textbf{k}-совершенных чисел на отрезке \textbf{\[l, r\]}. \InputFile В первой строке входного файла задано количество тестов \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{100000}). Каждый тест состоит из одной строки, содержащей три целых числа \textbf{l}, \textbf{r} и \textbf{k}, разделенных одним пробелом (\textbf{1} ≤ \textbf{l} ≤ \textbf{r} ≤ \textbf{10^6}, \textbf{0} ≤ \textbf{k} ≤ \textbf{10^9}). \OutputFile Для каждого теста выведите строку, содержащую количество \textbf{k}-совершенных чисел на отрезке \textbf{\[l, r\]}.