Divisible Pairs

All submissions for this problem are available.
Given N and M Dexter wants to know how many pairs a,b(1 <= a < b <=N) are there such that (a+b) is divisible by M.
For example when N=4 and M=3, there are 2 possible pairs the sum of which is divisible by M and they are (1,2) and (2,4).
Input
First line of input contains T(<=100000) which is the number of test cases. Each of the next T lines contains two integers N(1 <= N <= 10^9) and M(2 <= M <= 10^9).
Output
Output one line per testcase, the number of pairs (a,b) as described before.
Example
Input: 3 2 3 4 3 1 6 Output: 1 2 0
Author:  rustinpiece 
Tester:  subra 
Editorial  http://discuss.codechef.com/problems/DIVPAIR 
Tags  may12 medium rustinpiece 
Date Added:  11032012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
@admin in the case of N=4,M=3
@dey_jayanta : 1<=a < b<=n
thanks....
can a and b be both equal ??
@ dey_jayanta is 5<=4 ??
@krans4udo u know the
wow getting TLE....:'(
how to get over this time
indeed i have checked moi
got TLE with cout, and AC
@altaf : check
@vladamg98 m>=2 and m!=1
scanf("%lld")may have some
@Admin getting TLE please
@Admin getting TLE please
used 2 loops for and while
need some help ...how to deal
I am not using a single loop,
I am implementing an O(1)
There certainly is a problem
@admin please look into this
Got rid of TLE but now
is answer of n=10^9 and m=1
@chirayu and @s1aurabhpal_7 :
@admin: Since (1 <= a < b
@poojits for N=1, there does
ans for 10^9 2 is
I have used 2 loops except
I am getting this answer for
awesome..even for
i applied O(t*n*2) still
Anybody aware of any tricky
hey how to check moi code
i applied test case
can any one tell me what does
@altaf1148 : Each test file
@flying_ant i applied O(T)
@altal  Pls before posting
http://www.codechef.com/wiki/
@admin, I gave in the code
i am getting 1444150 for
please provide some more test
My code is working for 0,1
I am using o(1) and still
getting TLE ...used long
i am getting runtime
My code may or may not be
getting TLE in O(1)
can anyone tell the answer
@ridder I get for n = 10^9
I'm getting
my program is working for all
finally solved it.....had to
@ricola86thanks, i guess
@admin: plz reply to queries
Finally got it, well happy.
My code is working on all
@vladamg98: if you are coding
finally did it !!!
@Yogendra Mishra. thank you
hah, finally got AC !!! :)
@gskhirtladze : what was your
still getting WA :( have
please give correct answer
alaS! i Got AC!!!
@gskhirtladze yes i'm using
@ambuj  Yes.
is the largest answer
finally finally got accepted
@amrendrakumar ya it is
finally got CA......:))))
Finally got Accepted after 18
@thana  No.
@Illusion03 correct ans
i hv tried all the above
@Thana  Read the above
Same here. Each and every one
@Yogendra Mishra : You can
@Yogendra Mishra : You can not share the answers during a live contest. This may lead to disqualification
@All: Please do not share the
@All: Please do not share the answers/hints during a live contest. This may lead to disqualification.
@ADMIN Sorry for
grrr my brute force and O(1)
For N=10^9 and M=2, is the