题目描述

薯条哥的家乡最近推出了一种新型彩票，规则非常有趣：如果一个数字中，隐藏着一个连续的子串，且这个子串代表的数是$3$的倍数，

那么这个数字就是“幸运数字”。彩票每期都会公布一个范围$\left [ L,R \right ]$，并从这个范围的“幸运数字”中随机选择一个作为中奖号码。

以下是一些例子，辅助理解“幸运数字”的含义：

1. $107$是“幸运数字”：$0$是$107$的子串，且$0$是$3$的倍数
2. $25$不是“幸运数字”：$25$有$3$个子串分别是$2、5、25$，它们都不是$3$的倍数
3. $2521$是“幸运数字”：$21$是$2521$的子串，且$21$是$3$的倍数

注意子串必须是连续的，例：在数字$152$中，$15$是子串，$12$不是子串 以$0$开头的子串需要抹去先导$0$来考虑数值，

例：在数字$103$中，$03$是一个子串，它的值为$3$，也是$3$的倍数

薯条哥想知道$\left [L,R \right ]$中有多少个幸运数字，你能帮帮他吗

输入描述

有多个测试用例。输入的第一行包含一个整数$T(1\le T\le 10^4)$，表示测试用例的数量；

每组输入仅一行，包含两个整数$L,R(1\le L\le R\le 10^{18})$

输出描述

对每个测试用例，输出一个整数，表示区间$\left [L,R \right ]$中“幸运数字”的个数

样例

输入

2
8 19
2 45

输出

8
31