#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25;
typedef long long LL;
LL f[N][10]; // f[i][j] 表示最高位是j的i位数中,满足条件的数的数量
int digit[N];
LL n;
LL sum(LL n) {
int len = 0;
LL res = 0;
while (n) {
digit[++ len] = n % 10;
n /= 10;
}
digit[len + 1] = 0;
for (int i = len; i >= 1; i -- ) {
for (int j = 0; j < digit[i]; j ++ )
if (!(j == 9 && digit[i + 1] == 4))
res += f[i][j];
if (digit[i + 1] == 4 && digit[i] == 9)
break;
}
return res;
}
int main() {
f[0][0] = 1;
for (int i = 1; i < N; i ++ )
for (int j = 0; j <= 9; j ++ )
for (int k = 0; k <= 9; k ++ )
if (!(j == 4 && k == 9))
f[i][j] += f[i - 1][k];
int T;
scanf("%d", &T);
while (T -- ) {
scanf("%lld", &n);
printf("%lld\n", n + 1 - sum(n + 1));
}
return 0;
}
/*
f[数位][截止到第i位前面的连续奇数的次数][截止到第i位前面的连续偶数的次数]
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
typedef long long LL;
LL f[N][N][N];
int digit[N];
LL l, r;
int casei;
LL dfs(int pos, int p, int q, int limit) {
if (!pos)
return (!p || !(p & 1)) && (!q || (q & 1));
if (!limit && f[pos][p][q] != -1)
return f[pos][p][q];
int d = limit ? digit[pos] : 9;
LL res = 0;
for (int i = 0; i <= d; i ++ ) {
if (!p && !q && !i)
res += dfs(pos - 1, 0, 0, i == d && limit);
else if ((i & 1) && (p || q & 1 || (p == 0 && q == 0)))
res += dfs(pos - 1, p + 1, 0, i == d && limit);
//i为奇数时,可以是,1.新开始一段奇数那么前面的偶数个数得是奇数个,2或者延续前面的奇数那么p不为0,3.前导0
else if (!(i & 1) && (q || !(p & 1) || (p == 0 && q == 0)))
res += dfs(pos - 1, 0, q + 1, i == d && limit);
//i为偶数数时,可以是,1.新开始一段偶数那么前面的奇数数个数得是偶数个,2或者延续前面的偶数数那么f2不为0,3.前导0
}
if (!limit)
f[pos][p][q] = res;
return res;
}
LL sum(LL x) {
int pos = 0;
while (x) {
digit[ ++ pos] = x % 10;
x /= 10;
}
return dfs(pos, 0, 0, 1);
}
int main() {
memset(f, -1, sizeof f);
int T;
scanf("%d", &T);
while (T -- ) {
scanf("%lld%lld", &l, &r);
printf("Case #%d: %lld\n", ++ casei, sum(r) - sum(l - 1));
}
return 0;
}
/*
f[数位][支点编号][力矩和]
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
typedef long long LL;
LL f[N][N][1900];
int digit[N];
LL l, r;
LL dfs(int pos, int p, int q, int limit) {
if (!pos) {
if (!q)
return 1;
else
return 0;
}
if (q < 0)
return 0; // 加速
if (!limit && f[pos][p][q] != -1)
return f[pos][p][q];
int d = limit ? digit[pos] : 9;
LL res = 0;
for (int i = 0; i <= d; i ++ )
res += dfs(pos - 1, p, q + i * (pos - p), limit && i == d);
if (!limit)
f[pos][p][q] = res;
return res;
}
LL sum(LL x) {
int pos = 0;
while (x) {
digit[ ++ pos] = x % 10;
x /= 10;
}
LL ans = 0;
for (int i = 1; i <= pos; i ++ )
ans += dfs(pos, i, 0, 1);
return ans - pos + 1; // 0, 00, 000, ......
}
int main() {
memset(f, -1, sizeof f);
int T;
scanf("%d", &T);
while (T -- ) {
scanf("%lld%lld", &l, &r);
printf("%lld\n", sum(r) - sum(l - 1));
}
return 0;
}