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 M-1 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.
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.
For each test case, output a single line containing the answer.
- 1 ≤ T ≤ 105
- 1 ≤ M,N ≤ 108
Input: 1 2 3 Output: 2
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions