TRENDGCD - Trending GCD

Problem statement is simple. Given A and B you need to calculate S(A, B).

sigma(a=1 to A)sigma(b=1 to B) (a*b*f(gcd(a,b)))

Here, f(n)=n, if n is square free otherwise 0. Also f(1)=1.

Input

The first line contains one integer T - denoting the number of test cases.

T lines follow each containing two integers A, B.

Output

For each testcase output the value of S(A, B) mod 1000000007 in a single line.

Constraints

  • T <= 1000
  • 1 <= A, B <= 1000000

Example

Input:
3
42 18
35 1
20 25

Output:
306395
630
128819

Added by:Adarsh kumar
Date:2016-01-04
Time limit:0.300s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2019-09-25 11:15:34
The intended solution is supposed to be O(N+T*N^1/2)
2016-06-03 02:53:21 rainy jain
@Adarsh what is the expected complexity?
2016-04-18 23:26:05
getting TLE any suggestion
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.