JZPEXT - Beautiful numbers EXTREME

no tags 

We call one integer beautiful, if and only if it is divisible by each of its non-zero digits. Given an interval [l, r], calculate how many beautiful numbers n satisfy l<=n<=r.

Input

Then t lines follow, each line two numbers l, r, representing the query interval [l, r]

First line, the number of test cases, t.

Then t lines follow, each line two numbers l, r, representing the query interval [l, r].

1<=t<=2.5*10^4

1<=l<=r<=10^18

Output

t lines. The t-th line is the answer to the t-th query.

Example

Input:
1
1 100
Output:
33

hide comments
deva_raut: 2017-09-09 12:36:06

can someone give me an optimized code my code is running but the time complexity for large input is very high

Scape: 2015-07-21 17:42:58

What is the damn purpose of this problem? And why the hell source limit? I wasted 2 hours optimizing my solution only to find out it's too long. Got AC afterwards but this problem sucks hard.

Sourangsu : 2013-12-12 11:05:36

Not much fun in solving this...

Last edit: 2013-12-12 11:06:35
South_stream: 2013-09-01 14:04:16

who can tell me the real answer....I can't do it .. TLE always..

[Rampage] Blue.Mary: 2012-01-30 15:44:50

Resource: Codeforces Beta Round #55.

BTW, I don't like this problem. It needs heavy constant optimization, for example, I use array u[][] to store the result of (a*10+b)%C. (C is some constant.)

Last edit: 2012-01-30 16:38:21

Added by:sevenkplus
Date:2011-01-17
Time limit:0.114s
Source limit:1024B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All