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}$$$ (note that $$$0 \equiv x \pmod{3}$$$ means that $$$x$$$ is divisible by $$$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^5)$$$.
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^6})$$$.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Test $$$1 - 2$$$ satisfies $$$T \leq 10, R \leq 100$$$.
Test $$$3 - 5$$$ satisfies $$$T \leq 10, R \leq 1000$$$.
Tests $$$5 - 10$$$ satisfies $$$T \leq 10, R \leq 10^5$$$.
Tests $$$11 - 13$$$ satisfy $$$L = 1$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, output a new line containing a single integer $$$S$$$, denoting the desired sum modulo $$$998244353$$$.
511011003040336633666633
24 14808 130 512 767342710
Problem Idea: 3366
Problem Preparation: 3366
Occurrences: Novice 10
