BALNUM - Balanced Numbers

no tags 

Balanced numbers have been used by mathematicians for centuries. A positive integer is considered a balanced number if:

  1. Every even digit appears an odd number of times in its decimal representation
  2. 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 <= 1019 

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: 2023-08-22 20:03:57

MUST TRY https://www.spoj.com/problems/NUMTSN/ before solving this problem.
Both are mind-blowing problems.

spark_7: 2022-01-28 11:01:34

A very interesting problem.

yogeshk972: 2019-08-17 10:31:27

time limit is strict ! A small factor in complexity gave me tle

Last edit: 2019-08-17 10:33:55
[Rampage] Blue.Mary: 2017-08-30 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: 2014-11-06 22:31:18

awesome problem :) !!

Piyush Kapoor: 2012-05-10 22:11:04

@Buda IM: I completely agree with you ,test cases should be mentioned in the problem description.

Buda IM (retired): 2012-03-30 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: 2012-02-13 15:41:24

You may assume a thousand.

Saransh Bansal: 2012-02-13 12:49:14

How many test cases are there?


Added by:Angel Paredes
Date:2012-02-12
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