CODESPTA - 2s Complement

no tags 

One of the basics of Computer Science is knowing how numbers are represented in 2's complement. Imagine that you write down all numbers between A and B in 2's complement representation using 32 bits. How many 1's will you write down in all?

Input

The first line contains the number of test cases T. Each of the next T lines contains two integers A and B.

Output

Output T lines, one corresponding to each test case.

Constraints:

-231 <= A <= B <= 231 - 1

Sample

Input:
3
-2 0
-3 4
-1 4

Output:
63
99
37

Explanation

For the first case, -2 contains 31 1's followed by a 0 whereas -1 contains 32 1's. Thus the total is 63.

For the second case, the answer is 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99


hide comments
anurag garg: 2014-04-09 09:56:38

nice and easy my 300th on spoj...:)

Ashutosh Singla: 2013-05-25 19:02:22

overflows. :<

pardeep kumar: 2013-05-03 09:07:00

time limit is strict

Last edit: 2013-05-03 09:07:40
preetam: 2013-02-02 16:25:44

woohoooo... AC :)

Aditya Pande: 2013-01-04 12:24:56

WA and i don't know why?
got it. beware of overflows

Last edit: 2013-01-04 12:40:13
ɥsǝןǝǝu: 2012-10-26 05:28:33

O(b-a) will not pass....

Shubham Pandey: 2012-10-25 17:24:10

@Varun
Showing WA again and again.
Answer is correct.
why ?

__KIRA__: 2012-01-27 17:23:17

@Varun can u tell me whr my code fail's. wa everytime. solving test cases fine still wa! why ??
id 6405006

Last edit: 2012-01-27 17:24:31
BOND: 2011-12-18 23:12:38

time limit is really very strict.


Added by:Varun Jalan
Date:2011-10-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem used for CodeSprint - InterviewStreet Contest