题目描述

Volodya 认为一个数字 $x$ 是美丽的，当且仅当 $x\in\mathbb{Z^+}$ 并且对于 $x$ 的每一个非零位上的数 $y$，都有 $y|x$。

你需要帮助他算出在区间 $[l,r]$ 中有多少个数是美丽的。

输入格式

第一行包含一个整数 $t$，表示 $t$ 组数据，$1\le t\le 10$。

每组测试数据包含两个整数 $l,r$，$1\le l\le r\le 9\times 10^{18}$。

输出格式

对于每一组数据，在一行中输出一个整数表示答案。

1
1 9

9

1
12 15

2