题目描述

如果一个数对 $ (x,y) $ 是无聊的，当且仅当 $ x\leq y$，且 $ x~ \mathrm{xor}~y$ 的二进制表示下有奇数个 $ 1$。

如果让你求 $[1,n]$ 内的所有无聊的数对，那实在是太简单辣！

所以为了使得题目毒瘤一点，给出 $n$ 个区间 $[l_i,r_i]$，你需要数出有几对无聊的数 $(x,y)$ 满足 $x$ 和 $y$ 都在 $ [l_1,r_1] \cup [l_2,r_2]... \cup [l_i,r_i]$，即两个数都在前 $ i $ 个区间的并里。

输入格式

第一行一个正整数 $ n$；

接下来 $ n$ 行每行两个整数 $ [l_i,r_i]$，表示第 $ i$ 个区间，保证 $ l_i\leq r_i$。

输出格式

输出$ n$ 行，第$ i$ 行一个整数表示有几对无聊的数 $ (x,y)$ 满足 $ x,y$ 都在前 $ i $ 个区间的并里。

样例

input

5
1 7
3 10
5 7
4 111
222 12838

output

12
25
25
3080
40500496

数据范围与提示

对于 $ 30\%$ 的数据，有 $ 1\leq n\leq 100$, $1\leq l_i\leq r_i \leq 100$；

对于 $ 50\%$ 的数据，有 $1\leq n\leq 1000$，$1\leq l_i \leq r_i \leq 2^{32}-1$；

对于 $ 100\%$ 的数据，有 $1\leq n \leq 10^5$, $1\leq l_i \leq r_i \leq 2^{32}-1$。