题目描述

须弥是位于提瓦特大陆中西部的学城之都，无数智慧的果实在这里生长。教令院是位于须弥境内的学术机构，统筹管理须弥的所有事物，发布各种学术研究。

今年是$\text{2023}$年，须弥的学者注意到它的二进制表示为$11111100111$，恰好含有$2$个$0$，因此学者们认为今年是吉祥年，类似的，$\text{2013}$年也被认为是吉祥年，因为它的二进制表示为$11111011101$。

须弥的学者想知道，对于第l年到第r年，有多少个年份是吉祥年，因为学者很多，所以会有q次询问。

输入格式

第$1$行一个正整数$q$，表示询问的数量。

接下来$q$行，每行两个整数$l_i$和$r_i$，表示一次询问。

输出格式

共$q$行，每行两个整数表示询问的答案。

样例

3 
1 10 
2013 2023 
998244353 11451419260817

3 
3 
8630

数据范围

对于$40\%$的数据，$q,r_i\le 10^3$。

对于另外$40\%$的数据，$q=1$.

对于$100\%$的数据，$1\le q\le 10^5，1\le l_i\le r_i\le 2^{60}$.