You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

ComistryMo暑假打通了P5R之后，意外获得了怪盗团的力量，穿越到了异世界。但是他没有进行二周目，给邪恶的大人们发出预告信，而是沉迷于大富翁。

但是他太菜了！以至于芳泽霞学妹必须给ComistryMo放牌！ 作为团长，为了捍卫自己的威严，他决定与怪盗团成员玩数学游戏来取代大富翁。

他出的题目是这样的：给定T组数据，每组数据包含两个整数n,m，请求出$\sum_{i=1}^n$$\sum_{j=1}^m$ gcd(i,j)。

但是ComistryMo不会做这个题目，因此他想请聪明的你们来帮助他，解决此题，维护团长的尊严！

作为热心的怪盗团团长，joker告诉你们gcd(a,b)表示a与b的最大公因数。

Input Format

第一行一个整数T

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

Output Format

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

Sample

样例输入

3
100 200
1000 2000
1000000 2000000

样例输出

63542
9067212
17457854316166

Hint

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