互质数对

题目描述

$T$组询问，每次给两个数$n, m$，求有多少对$(i,j)$满足$1\leq i \leq n, 1\leq j \leq m$并且$i, j$互质。

输入格式

第一行一个整数$T$。

接下来$T$行，每行两个整数$n, m$。

输出格式

一共$T$行，每行一个数，表示答案。

样例输入

3
100 200
1000 2000
1000000 2000000

样例输出

12203
1216677
1215854454422

数据范围

对于所有数据，保证$1\leq T\leq 1000, 1\leq n,m \leq 10^7$。