[R11D]山谷数 - 代码源竞赛平台

时空限制

1S/512M

题目描述

称数字 $X$ 从低位到高位的第 $i$ 个数位为 $X_i$，例如对于 $X=420$，有 $X_1=0$，$X_2=2$，$X_3=4$。

记数字 $X$ 的数位共有 $len(X)$ 个，如果 $X_1=X_{len(X)}$ 且至少存在一个满足 $1< i< len(X)$ 的整数 $i$ 使得以下两个条件同时成立，称 $X$ 为山谷数：

• 对于满足 $1\leq j< i$ 的任意整数 $j$，有 $X_{j}>X_{j+1}$；
• 对于满足 $i\leq j< len(X)$ 的任意整数 $j$，有 $X_{j}<X_{j+1}$。

有 $q$ 个询问，第 $i$ 个询问求 $L_i\sim R_i$ 中有多少个山谷数。

格式

输入格式

第一行包含一个整数 $q$ 表示询问的数量。

接下来 $q$ 行每行包含两个整数 $L_i,R_i$，表示一个询问。

输出格式

输出 $q$ 行，每行一个整数，第 $i$ 个整数为第 $i$ 个询问的答案。

样例

样例输入 #1

1
2013 3034

样例输出 #1

3

样例解释 #1

$2013\sim 3034$ 中有以下 $3$ 个山谷数：$2102$、$3013$、$3023$。

样例输入 #2

5
98765432123456789 98765432123456789
98765432113456789 98765432113456789
1 10000000
1 1000000000000000000
1 100

样例输出 #2

1
0
10695
116504
0

数据规模

对于 $40\%$ 的数据，$R_i\leq 10^7$。

另有 $20\%$ 的数据，$L_i=1$。

对于 $100\%$ 的数据，$1\leq q\leq 3\times 10^5$，$1\leq L_i\leq R_i\leq 10^{18}$。