The difference between the Easy and Hard versions is the constraints on $$$T$$$ and $$$R$$$.
Utena really likes the number $$$3$$$. Let $$$f(x)$$$ count the number of $$$3$$$'s in the base-$$$10$$$ representation of $$$x$$$.
Given two integers $$$l$$$ and $$$r$$$ where $$$l \leq r$$$, compute $$$g(l, r)$$$, the sum of $$$f(x)$$$ for all $$$x$$$ such that $$$l \leq x \leq r$$$ and $$$0 \equiv x \pmod{3}$$$. That would have been the problem but Utena forgot what $$$l$$$ and $$$r$$$ were.
So given $$$L$$$ and $$$R$$$, compute the sum of $$$g(l, r)$$$ for $$$L \leq l \leq r \leq R$$$. Since this number may be very large, please find it modulo $$$998244353$$$.
The first line of input contains a single integer $$$T$$$, denoting the number of test cases $$$(1 \leq T \leq 10)$$$.
Each test case consists of two lines. The first line contains an integer $$$L$$$ and the second line contains an integer $$$R$$$ $$$(1 \leq L \leq R \leq 10^{10^5})$$$.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Test $$$1$$$ satisfies $$$R \leq 100$$$.
Test $$$2 - 3$$$ satisfies $$$R \leq 1000$$$.
Tests $$$4 - 5$$$ satisfy $$$R \leq 10^5$$$.
Tests $$$6 - 8$$$ satisfy $$$L = 1, R = 10^k$$$ for some integer $$$k$$$.
Tests $$$9 - 11$$$ satisfy $$$L = 1$$$.
Tests $$$12 - 14$$$ satisfy $$$\lceil \log_{10}(R) \rceil \leq 10^3$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, output a new line a containing single integer $$$S$$$, denoting the desired sum modulo $$$998244353$$$.
511011003040336633666633
24 14808 130 512 767342710
Problem Idea: 3366
Problem Preparation: 3366
Occurrences: Advanced 12
