题目描述

众所周知，所有OIer都喜欢形式化题面。

Q组询问，每组询问形如：给定非负整数 $l,r$ ，对于每个非负整数 $k$ ($0\leq k\leq 30$)，求有多少组整数对 $(x,y)$ 满足：$l\leq x\leq y$，$x$ $xor$ $y$ 共有k个二进制位为1。此处$xor$表示按位异或运算。

各组询问相互独立。

输入格式

Q行，每行31个正整数表示对于$k=1，2，\dots，30$ 时的整数对数，中间用空格分隔。

样例

样例输入1

1
2 5

样例输出1

4 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例解释

对于$k\geq4$，显然无满足条件的整数对

对于$k=3$，有$（2，5），（3，4）$

对于$k=2$，有$（2，4），（3，5）$

对于$k=1$，有$（2，3），（4，5）$

对于$k=0$，有$（2，3），（3，3），（4，4），（5，5）$

数据范围

对于所有数据，满足$1\leq Q\leq 5\times10^3$，$0\leq l,r\leq10^9$