Problem Description

定义一个函数 $\mu(x)$：如果 $x$ 等于 $k$ 个不同的质数的乘积，则 $\mu(x)=(-1)^k$，否则(即 $x$ 有大于 1 的平方因子) $\mu(x)=0$

定义 $lcm(a,b)$ 为 $a,b$ 的最小公倍数，给定 $n,m$，你需要求：

$\sum_{i=1}^{n}\sum_{j=1}^{m}\mu(lcm(i,j))$

Input

第一行一个正整数 $T(T\leq 10)$ 表示数据组数

接下来 $T$ 行，每行两个正整数 $n,m(1\leq n,m\leq 10^6)$，表示一次询问

Output

输出 $T$ 行，每行一个整数表示该组数据的答案

2
2 4
5 5

-2
-2