须弥吉祥年

题目背景

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

题目描述

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

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

输入格式

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

接下来 q 行，每行两个整数 li , ri 表示一次询问。

输出格式

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

样例 #1

样例输入 #1

3
1 10
2013 2023
998244353 11451419260817

样例输出 #1

3
3
8630

提示

对于 40% 的数据，q,ri<=10^3 。

对于另外 40% 的数据，q=1 。

对于 100% 的数据，1<=q<=10^5 , 1<=li<=ri<=2^60 。