It is known that the number is called perfect if it equals the sum of all its positive divisors except himself. For example, the first perfect number -- \textbf{6 = 1 + 2 + 3}. We now state this more rigorously, we consider the function: \includegraphics{https://static.e-olymp.com/content/9a/9a0eb405326f047983fb4f3ba4d68cc201bca30f.jpg} The number is perfect if and only if \textbf{σ(n) -- n = 0}. Is the number of \textbf{k}-perfect if \textbf{|σ(n) -- n| = k}. Thus, \textbf{2}-perfect numbers are, for example, \textbf{3} and \textbf{10}. Your task is to find the number of \textbf{k}-perfect numbers on the interval \textbf{\[l, r\]}. \InputFile The first line of the input file contains the number of tests \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{100000}). Each test consists of one line containing three integers \textbf{l}, \textbf{r} and \textbf{k}, separated by single spaces (\textbf{1} ≤ \textbf{l} ≤ \textbf{r} ≤ \textbf{10^6}, \textbf{0} ≤ \textbf{k} ≤ \textbf{10^9}). \OutputFile For each test case output a string containing the number of \textbf{k}-perfect numbers on the interval \textbf{\[l, r\]}.