神犇YY虐完数论后给傻×kAc出了一题

给定N, M,求 $1\le x\le N$ , $1\le y\le M$ 且 \(\gcd(x, y)\) 为质数的 \((x, y)\) 有多少对

kAc这种傻×必然不会了，于是向你来请教……

多组输入

第一行一个整数 \(T\) 表述数据组数

接下来 \(T\) 行，每行两个正整数，表示 \(N, M\)

\(T\) 行，每行一个整数表示第 \(i\) 组数据的结果

$T = 10000 $

\(N, M \le 10190000\)