Balanced numbers have been used by mathematicians for centuries. A positive integer is considered a balanced number if:

1)      Every even digit appears an odd number of times in its decimal representation

2)      Every odd digit appears an even number of times in its decimal representation

For example, 77, 211, 6222 and 112334445555677 are balanced numbers while 351, 21, and 662 are not.

Given an interval [A, B], your task is to find the amount of balanced numbers in [A, B] where both A and B are included.

Input

The first line contains an integer T representing the number of test cases.

A test case consists of two numbers A and B separated by a single space representing the interval. You may assume that 1 <= A <= B <= 1019 

Output

For each test case, you need to write a number in a single line: the amount of balanced numbers in the corresponding interval

Example

Input:
2
1 1000
1 9
Output:
147
4

刚开始题意看错了，以为是偶数出现奇数个，奇数出现偶数个，（自己太zz了）；

应该是每个偶数都出现奇数个，每个奇数都出现偶数个这才算是一个平衡数

由于是每个数字出现的次数，那么可以用状压的方法来记录状态，一个数字的出现无非三种情况，0没出现过，1出现次数为奇数次，2出现次数为偶数次，那么可以用三进制来压缩，0-9一共十个数字，共有种状态，所以dp[20][+1]就够了

难点就是压缩记录状态的步骤，详见代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
int a[20],sum[10];
ll dp[20][60000];
int update(int s,int n)
{
    memset(sum,0,sizeof(sum));
    for(int i=0;i<=9;i++)
    {
        sum[i]=s%3;
        s/=3;
    }
    if(sum[n]==0)sum[n]=1;
    else sum[n]=3-sum[n];
    int ss=0,xx=1;
    for(int i=0;i<=9;i++)
    {
        ss=ss+sum[i]*xx;
        xx*=3;
    }
    return ss;
}
int judge(int x)
{
    for(int i=0;i<=9;i++)
    {
        int ss=x%3;
        x/=3;
        if(i%2==0&&ss==2)return 0;
        if(i%2==1&&ss==1)return 0;
    }
    return 1;
}
ll dfs(int pos,int sta,int limit)
{
    if(pos==0){
        if(judge(sta))return 1;
        return 0;
    }
    if(!limit&&dp[pos][sta]!=-1)return dp[pos][sta];
    int up=limit?a[pos]:9;
    int ans=0;
    for(int i=0;i<=up;i++)
    {
        ans += dfs(pos - 1,sta==0&&i==0?0:update(sta,i), limit && i == up);
    }
    if(!limit) dp[pos][sta]=ans;
    return ans;
}
ll solve(ll x)
{
    int t=0;
    while(x)
    {
        a[++t]=x%10;
        x/=10;
    }
    return dfs(t,0,1);
}
int main()
{
    int T;
    memset(dp,-1,sizeof(dp));
    cin>>T;
    while(T--)
    {
        ll l,r;
        cin>>l>>r;
        printf("%lld\n",solve(r)-solve(l-1));
    }
    return 0;
}