提示: 欢迎访问OurACM平台
Problem 2071 lucky number

Accept: 104    Submit: 267
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

A positive integer number is lucky if and only if any three digits of it are not increasing or decreasing, and any two digits of it are different. The numer that has less than three digits is lucky number if no two digits of it are the same. For example, 123 and 321 are not lucky numbers. 132 is a lucky number. please count the quantity of lucky 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 ≤ 1000000) .

Output

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

Sample Input

3 1 10 1 100 1 200

Sample Output

10 90 134

Source

FOJ有奖月赛-2011年12月

Submit  Back  Status  Discuss