PROG0031 - VII

An integer $n$ is called a good number if it meets at least one of the following two conditions:

  • $n$ is divisible by 7 
  • the digit 7 occurs in $n$
Determine how many good numbers occur in a given interval.

Input

The input consists of $t$ test cases ($t \leq 200$). The first line of the input contains an integer $t$. Then the description of the $t$ test cases follows. Each description of a test case contains one single line that contains the integers $a$ and $b$ ($0 \leq a < b \leq 100.000$), separated by one single space.

Output

For each test case, determine how many good numbers $n$ exist where $a \leq n \leq b$.

Example

Input:

5
12 930
9239 81736
7837 90943
636 33771
0 100000

Output:

349
37189
41901
14349
49386

Een natuurlijk getal $n$ wordt een goed getal genoemd als aan minstens één van volgende twee voorwaarden voldaan is:

  • $n$ is deelbaar door 7 
  • het cijfer 7 komt voor in $n$
Bepaal hoeveel goede getallen er in een gegeven interval gelegen zijn.

Invoer

De invoer bestaan uit $t$ testgevallen ($t \leq 200$). De eerste regel van de invoer bevat een natuurlijk getal $t$. Daarna volgt de omschrijving van de $t$ testgevallen. Elke omschrijving van een testgeval bestaat uit één enkele regel die de natuurlijke getallen $a$ en $b$ bevat ($0 \leq a < b \leq 100.000$), van elkaar gescheiden door één enkele spatie.

Uitvoer

Bereken voor elk testgeval hoeveel goede getallen $n$ er bestaan waarvoor $a \leq n \leq b$.

Voorbeeld

Invoer:

5
12 930
9239 81736
7837 90943
636 33771
0 100000

Uitvoer:

349
37189
41901
14349
49386

Added by:Peter Dawyndt
Date:2011-07-20
Time limit:30s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.