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