CNT_LUCK - Counting Lucky Numbers

Find out how many numbers between a and b (inclusive) when represented as binary numbers have sum of digits lucky.

A number is lucky if its decimal representation contains digits 4 and 7 only.

eg. 4, 7, 47, 77 etc. where as 14, 41 etc. are not.

Note that 0 <= a <= b <= 10^19.

Input

T: number of test cases T<=10^5

Next T lines have a and b in every line. a <= b

Output

for every test case output as described in problem statement

Example

Input:
2
15 15
63 63

Output:
1
0

Added by:praveen123
Date:2013-01-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:general

hide comments
2016-06-22 07:56:36
Take care of the case when a=b=0.Answer must be 0.
2015-08-24 12:42:49 Medo
I passed a 10000 random generated test cases against an AC code however I keep getting a WA...

Edit: SAME code submitted in C++14 instead of C++ 5 gives AC. This is very stupid.

Last edit: 2015-08-24 12:53:50
2014-02-28 17:53:29 P_Quantum
nice prblm :)
2013-06-28 18:05:22 Utsav Sinha
Point to be Noted : "44" is a lucky number. Got WA due to it :(
But after considering it, got accepted :)

Last edit: 2013-06-28 18:10:03
2013-06-23 09:09:17 edoc
@pravin123 can we take input in c++ as unsigned long long.. or we are to use string??
2013-06-07 05:16:07 Kartik Khare
I am pretty much sure i have the correct solution but still not getting AC..
please help me.
my solution ID is 9434562
2013-02-22 10:00:20 Problem Solver
Please help with that :-) If you can, mail me knifemod at gmail or just give some test case here... Would greatly appreciate. thanks.
2013-02-22 10:00:20 Problem Solver
Thanks for an answer, but i still cant understand what could i misunderstood in contraits. Valuesfit in unsigned long long and are positive. Could you help me with that or point what am doing wrong? Thanks in advance...
2013-02-22 10:00:20 praveen123
@ Problem Solver , your code was not working on some test cases. I think that you have misunderstood the constraints , Please see the constraints.
Hint: not working on very small test cases
2013-02-22 10:00:20 Problem Solver
Very nice problem, but i'm having a little problem with this. I'm almost sure that i have correct solution. Although i can't get AC, this is my solution : 8662732
I've checked my original solution with brute force ( just uncomment last line to see it ) in range 1 to 10^5 with all correct answers. I can't contact you @ praveen123 other way, so if possible, please answer here! Thanks... Maybe some test??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.