题目思路

总的思路是：先二分找第 $l,r$ 个字符位于第几个数。然后差分计算两个数之间有多少个逗号和分号即可。

具体的：先实现一个函数，求第 $i$ 个数的最后一个数位，位于第几个字符。然后就可以轻松的使用二分答案求第 $i$ 个字符位于第几个数内。

这里注意，字符位于逗号/分号上，也算作它位于后面那一个数。具体细节见代码注释。

题目内容

在某个神秘的数字世界中，有一位数学家米小游。他是这个数字世界中最聪明的人，他喜欢研究各种数字规律。

今天，米小游得到了一个无限长的字符串，该字符串代表着整个自然数集。这个字符串由数字字符 , 和 ; 以及数字组成，其中每三个数字由一个分号隔开，其它的数字由逗号隔开。

具体字符串为：1,2,3;4,5,6;7,8,9;10,11,12;13,14...... 。

米小游对这个字符串产生了浓厚的兴趣，并想知道该字符串的第 $l$ 个字符到第 $r$ 个字符之间有多少个逗号和分号。

第一行输入一个正整数 $t$ ，代表询问次数。

接下来的 $t$ 行，每行输入两个正整数 $l$ 和 $r$ ，代表一次询问。

$1\le t\le 10^4$

$1\le l\le r\le 10^{12}$

输出 $t$ 行，每行输入两个整数，用空格隔开。

分别代表 , 的数量和 ; 的数量。

输入

2
3 6
8 10

输出

1 1
2 0

样例解释

第 $3$ 个字符到第 $6$ 个字符是 "2，3;" ，包含一个逗号和一个分号。

第 $8$ 个字符到第 $10$ 个字符是 ”，5，" ，包含 $2$ 个逗号，没有分号。