Classy Numbers

Let’s call some positive integer classy if its decimal representation contains no more than 3 non-zero digits. For example, numbers 4, 200000, 10203 are classy and numbers 4231, 102306, 7277420000 are not.

You are given a segment [L;R]. Count the number of classy integers x such that L≤x≤R.

Each testcase contains several segments, for each of them you are required to solve the problem separately.

Input

The first line contains a single integer T (1≤T≤104) — the number of segments in a testcase.

Each of the next T lines contains two integers Li and Ri (1≤Li≤Ri≤1018).

Output

Print T lines — the i-th line should contain the number of classy integers on a segment [Li;Ri].

Example

Input

4
1 1000
1024 1024
65536 65536
999999 1000001

Output

1000
1
0
2

题目给出多组测试用例，每组测试用例给定一个区间，你需要判断该区间中有多少个数字中包含的非零数字的数量不大 3
很显然，题目数据范围给的很大，直接暴力肯定超时，因此考虑到数位 DP ，（ 其实就是一个数位 DP 的模板题，哈哈哈嗝 ）
定义 f [ pos ][ cnt ] 表示在第 pos 位的状态时，cnt 表示该状态时非零数字的数量，约束状态就是 cnt <= 3 ，直接套模板就可以！

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=30;
int t;
ll l,r;
ll p[N];
ll f[N][4];

ll dp(int pos,int cnt,int flag)
{
	if(pos==-1) return 1;
	if(flag&&f[pos][cnt]!=-1) return f[pos][cnt];
	int ans=0;
	int up=flag?9:p[pos];
	for(int i=0;i<=up;i++)
	{
		if(cnt+(i!=0)>=4) break;
		// 当非零数字的个数超过3后，剩余未判断的状态也就不需要判断了，因为肯定是不合法的，直接 break 掉就可以了
		ans+=dp(pos-1,cnt+(i!=0),flag||i<up);
	}
	if(flag) f[pos][cnt]=ans;
	return ans;
} 

ll slove(ll x)
{
	int pos=0;
	while(x)
	{
		p[pos++]=x%10;
		x/=10;
	}
	return dp(pos-1,0,0);
}

int main()
{
	cin>>t;
	while(t--)
	{
		memset(f,-1,sizeof f);
		cin>>l>>r;
		ll ans=slove(r)-slove(l-1);
		cout<<ans<<endl;
	}
	return 0;
}