Відомо, що число називається досконалим, якщо воно дорівнює сумі усіх своїх додатніх дільників, крім нього самого. Наприкклад, перше досконале число -- \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\]}.