P7199 [COCI 2019/2020 #1] Trol

Stjepan 最近在萨格勒布大学获得了数学学士学位。他的父母自然而然地为他感到骄傲，并决定给他所有不超过 $2^{60}$ 的正整数作为礼物。为了保证它们的安全，他迅速地将所有数存入了一个序列 $A$，使得 $A_i=i$。 一个妒忌他的朋友 Marin 决定做一个恶作剧：**不断地把 $A$ 中的每个元素替换为其所有数位之和，直到最终只剩下一位数。** 例如，第 $197$ 个元素的初始值为 $197$。Marin 先将这个值变为 $1+9+7=17$，然后再一次改变了它，使其变为 $1+7=8$。 Stjepan 对此极为震惊，并请求 Marin 把序列变回初始状态。不幸的是，在他正确回答 $Q$ 个询问之前，Marin 并不会如此。对于每一个询问，Stjepan 需要回答 $A$ 序列中第 $l$ 项至第 $r$ 项元素的总和。 来帮 Stjepan 回答这些询问吧！

无

无

#### 数据规模及约定 对于 $20\%$ 的数据，所有询问满足 $1 \le l_i \le r_i \le 9$。 对于 $60\%$ 的数据，所有询问满足 $r_i-l_i \le 1000$。 对于 $100\%$ 的数据，$1 \le Q \le 100$，所有询问满足 $1 \le l_i \le r_i \le 2^{60}$。 #### 说明 **本题分值按 COCI 原题设置，满分 $50$。** **题目译自 [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #1](https://hsin.hr/coci/archive/2019_2020/contest1_tasks.pdf) _T1 Trol_ 。**