UOJ Logo

NOI.AC

1S 512MB

#327. link

Statistics

【问题描述】

对于一正整数N,首先将 N看做一个由数字组成的字符串(不带前导 0);然后,如果 N 的最后一个字符是 0,就去掉它,重复这一过程直到 N的最后一个字符不是 0;最后记 N的长度为 a。 如果此时 N的最后一位是 5,则N的相关数为 2 a - 1;否则为 2 a。

例如,850 的相关数为 3,而 880 则为 4,9999 的相关数为 8

现在给你一个数值[L, R] 范围,请你在该范围内找出相关数最低的那个数。

【输入格式】

输入文件的第一行包含一个正整数 T,表示测试数据的数目。 每个测试数据占单独的一行,包含两个空格分隔的正整数 L, R,表示数值范围。

【输出格式】

对于每个测试数据,在单独的一行内输出结果。 如果相关数最低的数不是唯一的,输出最小的那个。

【输入输出样例 】

in

3
998  1002
998  2002
4000  6000

out

1000
1000
5000

【数据规模与约定】

对于 20% 的数据,T ≤ 10,1 ≤ L ≤ R ≤ 1000。

对于 100% 的数据,T ≤ 100,1 ≤ L ≤ R ≤ 1000,000,000。