## RAONE - Ra-One Numbers

In the War between good and evil . Ra-One is on the evil side and G-One on the good side.

Ra-One is fond of destroying cities and its G-one's duty to protect them..

Ra-One loves to destroy cities whose Zip Code has special properties. He says he loves to destroy cities which have Ra-One numbers as their Zip Code.

Any number is Ra-one if the Difference between Sum of digits at even location and Sum of digits at odd location is One (1).. For eg... for 234563 is Ra-One number

digits at odd location are 3,5,3 (unit place is location 1 )

digits at even location are 2,4,6

Diff = (2+4+6)-(3+5+3)=12-11 = 1.

And 123456 is not Ra-One number

diff = (5+3+1) - (2+4+6) = -4

G-One knows this about Ra-one and wants to deploy his Army members in those cities. 1 army member will be deployed in each city.

G-one knows the range of ZIP-Codes where Ra-One might attack & needs your help to find out how many army members he needs.

Can you help Him ?

### Input

First line will have only one integer 't' number of Zip-Code ranges. it is followed by t lines

Each line from 2nd line contains 2 integer 'from'  and 'to'. These indicate the range of Zip codes where Ra-one might attack. ('From' and 'to' are included in the range)

NOTE:'t' will be less than 100. 'from' and 'to' will be between 0 and 10^8 inclusive.

### Output

A single number for each test case telling how many army members G-One needs to deploy.

each number should be on separate lines

### Example

```Input:
2
1 10
10 100

Output:
1
9
```

#### explanation:

for 1st test case the only number is 10

for 2nd test case numbers are 10, 21, 32, 43, 54, 65, 76, 87, 98

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

const int MAXN = 1e5+5;

string a, b;

ll dp[10][105][105][2];

int n;

ll solve(string &s, int idx, ll sumEven, ll sumOdd, int constructedPrefixIsEqualtoPrefix){
if(dp[idx][sumEven][sumOdd][constructedPrefixIsEqualtoPrefix] != -1)
return dp[idx][sumEven][sumOdd][constructedPrefixIsEqualtoPrefix];
ll res = 0;
if(idx == n){
res = (sumEven-sumOdd == 1) ? 1 : 0;
}else{
if(constructedPrefixIsEqualtoPrefix){
for(int i = 0; i <= s[idx]-'0'; i++){
if(i == s[idx]-'0'){
// if(idx&1)
//     res += solve(s, idx+1, sumEven, sumOdd + i, 1);
// else
res += solve(s, idx+1, sumOdd, sumEven + i, 1);
}
else{
// if(idx&1)
//     res += solve(s, idx+1, sumEven, sumOdd + i, 0);
// else
res += solve(s, idx+1, sumOdd, sumEven + i, 0);
}
}
}else{
for(int i = 0;i < 10; i++){
// if(idx&1)
//     res += solve(s, idx+1, sumEven, sumOdd + i, 0);
// else
res += solve(s, idx+1, sumOdd, sumEven + i, 0);
}
}
}
dp[idx][sumEven][sumOdd][constructedPrefixIsEqualtoPrefix] = res;
return res;
}

ll f(string& a){
ll sumOdd = 0;
ll sumEven = 0;
bool odd = true;
for(int i = (int)a.size()-1; i >= 0; i--){
if(odd){
sumOdd += a[i] - '0';
odd = false;
}
else{
sumEven += a[i] - '0';
odd = true;
}
}
return (sumEven-sumOdd == 1);
}

int main(){
io;
int t;
cin >> t;
while(t--){
cin >> a >> b;
memset(dp, -1, sizeof dp);
n = b.size();
ll ansR = solve(b, 0, 0, 0, 1);
memset(dp, -1, sizeof dp);
n = a.size();
ll ansL = solve(a, 0, 0, 0, 1);
ll ans = ansR - ansL + f(a);
cout << ans << endl;
}
return 0;
}``````
Copy The Code &

Input

cmd
2
1 10
10 100

Output

cmd
1
9