Problem: 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 ≤ 10^4) — the number of segments in a testcase.

Each of the next T lines contains two integers L_i and R_i (1 ≤ L_i ≤ R_i ≤ 10^{18}).

Output

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

Example

Input

4
1 1000
1024 1024
65536 65536
999999 1000001


Output

1000
1
0
2

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long C[19][19];
long long arr[19][4];
long long pls[4] = {1, 9, 81, 729};
int main() {
  int t, i, j, flag, len1, len2;
  char l[30], r[30];
  long long ans, num1, num2, num, temp;
  for (i = 0; i <= 18; i++) {
    for (j = 0; j <= min(i, 3); j++) {
      if (i == 0 || j == 0)
        C[i][j] = 1;
      else if (i == j)
        C[i][j] = 1;
      else
        C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
    }
  }
  for (i = 1; i <= 18; i++)
    for (j = 0; j <= 3; j++) arr[i][j] = C[i][j] * pls[j];
  for (i = 1; i <= 18; i++)
    for (j = 1; j <= 3; j++) arr[i][j] += arr[i][j - 1];
  arr[0][0] = arr[0][1] = arr[0][2] = arr[0][3] = 1;
  scanf("%d", &t);
  for (i = 0; i < t; i++) {
    scanf("%s%s", l, r);
    len1 = strlen(l);
    len2 = strlen(r);
    num1 = num2 = 0;
    num = 0;
    for (j = 0; j < len1; j++) {
      if (num >= 3) break;
      if (l[j] > '0') {
        num++;
        num1 += (l[j] - '1') * arr[len1 - j - 1][3 - num] +
                arr[len1 - j - 1][3 - num + 1];
      }
    }
    num = 0;
    for (j = 0; j < len2; j++) {
      if (num >= 3) break;
      if (r[j] > '0') {
        num++;
        num2 += (r[j] - '1') * arr[len2 - j - 1][3 - num] +
                arr[len2 - j - 1][3 - num + 1];
      }
    }
    ans = num2 - num1;
    num = 0;
    for (j = 0; j < len1; j++)
      if (l[j] != '0') num++;
    if (num <= 3) ans++;
    printf("%I64d\n", ans);
  }
}