# DIVCNTK - Counting Divisors (general)

## 题意翻译

$\sigma_0(i)$ 表示$i$ 的约数个数 求$S_k(n)=\sum_{i=1}^n\sigma_0(i^k)\mod 2^{64}$ 多测,$T\le10^4,n,k\le10^{10}$ Translated by @Kelin

## 题目描述

Let $\sigma_0(n)$ be the number of positive divisors of $n$ . For example, $\sigma_0(1) = 1$ , $\sigma_0(2) = 2$ and $\sigma_0(6) = 4$ . Let $$S_k(n) = \sum _{i=1}^n \sigma_0(i^k).$$ Given $n$ and $k$ , find $S_k(n) \bmod 2^{64}$ .

## 输入输出格式

### 输入格式

There are multiple test cases. The first line of input contains an integer $T$ ( $1 \le T \le 10000$ ), indicating the number of test cases. For each test case: The first line contains two integers $n$ and $k$ ( $1 \le n, k \le 10^{10}$ ).

### 输出格式

For each test case, output a single line containing $S_k(n) \bmod 2^{64}$ .

## 输入输出样例

### 输入样例 #1

5
1 3
2 3
3 3
10 3
100 3

### 输出样例 #1

1
5
9
73
2302