Find the sum

All submissions for this problem are available.
Bob is extremely bored, so he thinks of a game to play in the meanwhile. The game is as follows. He takes two integers N and M and tries to find twice the sum of the quotients of the integer division of (i * N) by M varying i from 0 to M1 both included. But as he started computing the sums for larger values of M and N, things started becoming very complex. So he has asked for your help. You need to output the sum that Bob needs.
Input
The first line of the input contains an integer T denoting the number of test cases.
Each of the next T lines contains two space separated integers M and N.
Output
For each test case, output a single line containing the answer.
Constraints
 1 ≤ T ≤ 10^{5}
 1 ≤ M,N ≤ 10^{8}
Example
Input: 1 2 3 Output: 2
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  7032013 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP 4.3.2, CPP 4.9.2, CPP14, GO, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
i have got pop up 'restricted
why did I can't submit?
@mod.... plz tell what's the
@cssumit, @steamqueen: You
@mod i had already register
@mod ????
@cssumit: then please login
twice means that when she
@iashabuxo_team: Yes
ok thanks just solve
Do we use %lld or %Id64 for
@seoul_garden  %lld works
how are we supposed 2 take
@paribhasika use Scanner
@paribhasika you can make use
@mod what does "integer
@avish1  Yes
each tym time limit exceed
each f***ing time it says
My program run perfectly in
Will long in java suffice ??
@artylusty: Yes
why is it giving wrong answer
@technocoding  The output
do we have to apply mod
@technocoding: Read the
can m>n ?
@hack_it: There is no order
In the Example Input: 1 2
@rebugger  m and n are given
TLE .... i dnt think it cab
@iupac_admin: Please tell how