UOJ Logo

NOI.AC

1S 512MB
Statistics

题目描述

本题提供形式化简洁题意,参见题目描述最后一行。

nz 国的居民发现了一个神奇的数列 $a$。一开始,$a_i$ 表示的数等于 $i$。到了第一天,这个数列发生了一些神奇的变化,每个 $a_i$ 都加上了 $i$ 在十进制表示中的个位数。第二天,每个 $a_i$ 都加上了 $i$ 在十进制表示中的十位数。这样不知过了多少天,一些 $a_i$ 就不再变化了。

nz 国的居民喜欢玩跳跳棋。发现这个数列后,人们制定了一个规则:从 $i$ 出发的跳棋,下一步要跳到第 $a_i$ 格。

你在很多天后来到 nz 国。nz 国的居民有 $q$ 个问题请教你,他们想知道棋子从 $x$ 出发走到第一次超过 $y$ 时,走到的位置。

形式化题意:$q$ 次询问,给出 $x,y$,重复将 $x$ 加上当前 $x$ 在十进制下的数位和,直到第一次 $x>y$ 时,输出 $x$ 的值。

输入格式

第一行一个整数 $q$。

接下来 $q$ 行每行两个整数 $x,y$。

输出格式

输出 $q$ 行表示答案。

样例输入

10
114514 1919810
13 22
100 200
200 300
300 400
998244353 1000000007
1000000009 1004535809
1 2
1 11
1 20

样例输出

1919842
25
218
317
408
1000000051
1004535812
4
16
23

数据范围

对于所有数据,满足 $1\le x\le y < 10^{10},1\le q\le 5\times 10^5$。

  • 子任务 1(20pts):$y\le 10^5$
  • 子任务 2(25pts):$y\le 10^7$
  • 子任务 3(25pts):$q\le 50$
  • 子任务 4(30pts):无特殊限制