/* import sys from collections import defaultdict input = sys.stdin.readline def main(): T = int(input()) for _ in range(T): L,R = input().split() L = str(int(L)-1) L_keta,R_keta = len(L), len(R) memo = defaultdict(int) def f(n, MAX, giri, R, R_keta): if(n == R_keta):return MAX if((n,MAX,giri) in memo):return memo[(n,MAX,giri)] ret = 0 if(giri): for i in range(int(R[n])+1): ret += f(n+1, max(MAX, i), int(R[n]) == i, R, R_keta) else: if(MAX == 9):return 9 * pow(10, R_keta - n) ret += f(n+1, MAX, False, R, R_keta) * (MAX+1) for i in range(MAX+1, 10): ret += f(n+1, i, False, R, R_keta) memo[(n,MAX,giri)] = ret return ret ans = f(0,0,True,R,R_keta) memo = defaultdict(int) ans -= f(0,0,True,L,L_keta) print(ans) main() */ #include #include #include #include using namespace std; // 10の累乗を整数で計算する関数(Pythonのpow(10, x)と同等) long long power_of_10(int exp) { long long res = 1; for (int i = 0; i < exp; ++i) { res *= 10; } return res; } int main() { // 標準入出力の高速化(sys.stdin.readline相当) ios_base::sync_with_stdio(false); cin.tie(NULL); int T; if (!(cin >> T)) return 0; for (int t = 0; t < T; ++t) { string L_str, R_str; cin >> L_str >> R_str; // L = str(int(L)-1) string L_val = to_string(stoll(L_str) - 1); int L_keta = L_val.length(); int R_keta = R_str.length(); // memo = defaultdict(int) // C++では未計算を -1 として扱うため、全要素を -1 で初期化 vector>> memo(20, vector>(10, vector(2, -1))); // def f(n, MAX, giri, R, R_keta) // ラムダ式を使用して再帰関数を定義 auto f = [&](auto& self, int n, int MAX, bool giri, const string& R, int R_keta) -> long long { if (n == R_keta) return MAX; // if((n,MAX,giri) in memo):return memo[(n,MAX,giri)] if (memo[n][MAX][giri] != -1) return memo[n][MAX][giri]; long long ret = 0; if (giri) { int r_n = R[n] - '0'; // 文字を数値に変換 for (int i = 0; i <= r_n; ++i) { ret += self(self, n + 1, max(MAX, i), r_n == i, R, R_keta); } } else { if (MAX == 9) return 9LL * power_of_10(R_keta - n); ret += self(self, n + 1, MAX, false, R, R_keta) * (MAX + 1); for (int i = MAX + 1; i < 10; ++i) { ret += self(self, n + 1, i, false, R, R_keta); } } // memo[(n,MAX,giri)] = ret memo[n][MAX][giri] = ret; return ret; }; // ans = f(0,0,True,R,R_keta) long long ans = f(f, 0, 0, true, R_str, R_keta); // memo = defaultdict(int) // Lの計算用にメモを -1 でリセット memo = vector>>(20, vector>(10, vector(2, -1))); // ans -= f(0,0,True,L,L_keta) ans -= f(f, 0, 0, true, L_val, L_keta); // print(ans) cout << ans << "\n"; } return 0; }