Description

对于正整数 $n$ ，记 $\sigma_2$ 为其所有约数的平方和，例如：

$\sigma_2(10) = 1 + 4 + 25 + 100 = 130$

现在给你两个整数 $N$ 和 $K$，其中 $1 \leqslant n \leqslant N$，有些 $n$ 可以满足： $\sigma_2(n)$ 和其最接近的完全平方数之差的绝对值最大不超过 $K$ 。

最接近的完全平方数是指该数和所有完全平方数之差的绝对值最小的那个完全平方数。

求所有满足条件的 $n$ 的和。

Input Format

输入第一行是一个整数 $q$ ，表示一共有 $q$ 次询问。

接下来有 $q$ 行，每行包含两个整数，即 $N$ 和 $K$ 。

其中 $1 \leqslant q \leqslant 10^5$ ， $1 \leqslant N \leqslant 10^6$ ， $0 \leqslant K \leqslant 10^5$ 。

Output Format

对于输入的 $N$ 和 $K$ 来说，输出所有满足条件的 $n$ 的和。

8 
5 1 
26 0 
31 2 
75 3 
157 4 
186 5 
1882 6 
4270 7

11
1
167
801
3594
4490
278015
1218448