提示: 欢迎访问OurACM平台。
Problem 2070 Beautiful number

Accept: 28    Submit: 88
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Seen is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if the sum of first half of the digits of it equal to the sum of after half of the digits of it. If a number have n digits, first half of the digits of it is the digits of first n/2.For example, 45 and123 are not beautiful numbers. 1423 and 321 are beautiful numbers. We will not argue with this and just count the quantity of beautiful numbers in given ranges.

Input

The first line of the input contains the number of cases t. Each of the next t lines contains two natural numbers li and ri (1 ≤ li ≤ ri ≤ 9*10^18) .

Output

Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from li to ri, inclusively).

Sample Input

3 1 10 1 100 1 200

Sample Output

0 9 11

Source

FOJ有奖月赛-2011年12月

Submit  Back  Status  Discuss