← 返回题目列表

Codeforces · 55/D

D. 美丽的数字

中文机器翻译题面 查看原题

Volodya 是一个奇怪的男孩,他的品味也很奇怪。在他看来,一个正整数是美丽的,当且仅当它可以被它的每个非零数字整除时。我们不会争论这一点,只是计算给定范围内美丽数字的数量。

输入

输入的第一行包含事例数 t (1 ≤ t ≤ 10)。接下来的 t 行中的每一行都包含两个自然数 li 和 ri (1 ≤ li ≤ ri ≤ 9 ·1018)。

请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin (也可以使用 %I64d)。

输出

输出应包含 t 个数字 - 查询的答案,每行一个数字 - 给定间隔内(从 li 到 ri,包含在内)内漂亮数字的数量。

示例

输入 #1

1
1 9

输出 #1

9

输入 #2

1
12 15

输出 #2

2