\begin{problem}{Divisors}{\textsl{standard input}}{\textsl{standard output}}{5 seconds}{256 mebibytes}{}

Lets denote $d_k(n)$ number of partitions $n$ as a product of $k$ integers (order is significant $1\cdot 2$ and $2\cdot 1$ are different partitions). You should calculate $\sum\limits_{i=1}^n f_k(i)$ for a given $n,k$.

\InputFile 

In the first line $T\leq 10^5$ -- numner of tests. Every testcase description consists of line line with two integers $0<n\leq 10^9$ and $0<k\leq 4$. Sum of all $n$ in testcases doesn't exceed $10^9$.

\OutputFile 

Single line with integer answer for every testcase.

\Examples
\begin{example}
\exmp{
4
3 1
4 2
5 3
6 4
}{
3
8
16
39
}%
\end{example}
\end{problem}


