BALNUM  Balanced Numbers
Balanced numbers have been used by mathematicians for centuries. A positive integer is considered a balanced number if:
 Every even digit appears an odd number of times in its decimal representation
 Every odd digit appears an even number of times in its decimal representation
For example, 77, 211, 6222 and 112334445555677 are balanced numbers while 351, 21, and 662 are not.
Given an interval [A, B], your task is to find the amount of balanced numbers in [A, B] where both A and B are included.
Input
The first line contains an integer T representing the number of test cases.
A test case consists of two numbers A and B separated by a single space representing the interval. You may assume that 1 <= A <= B <= 10^{19}
Output
For each test case, you need to write a number in a single line: the amount of balanced numbers in the corresponding interval
Example
Input: 2 1 1000 1 9 Output: 147 4
hide comments
shishank_93774:
20230822 20:03:57
MUST TRY https://www.spoj.com/problems/NUMTSN/ before solving this problem.


spark_7:
20220128 11:01:34
A very interesting problem. 

yogeshk972:
20190817 10:31:27
time limit is strict ! A small factor in complexity gave me tle Last edit: 20190817 10:33:55 

[Rampage] Blue.Mary:
20170830 06:54:04
The number of test cases is relatively "small", i.e. there won't be 1000 test cases with 19 digits number. 

Satyanveshi_Byomkesh_bakshy:
20141106 22:31:18
awesome problem :) !! 

Piyush Kapoor:
20120510 22:11:04
@Buda IM: I completely agree with you ,test cases should be mentioned in the problem description. 

Buda IM (retired):
20120330 09:19:05
I think number of test cases should be in problem description. Because you should know whether to do overkill by precalculating all results, or calc solution for each test alone. But usually authors leave out that number .. 

Angel Paredes:
20120213 15:41:24
You may assume a thousand. 

Saransh Bansal:
20120213 12:49:14
How many test cases are there? 
Added by:  Angel Paredes 
Date:  20120212 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: PERL6 
Resource:  Cuban Olympiad in Informatics 2012  Day 2 Problem A 