题目描述

如果一个数对 $(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$ 个区间的并里。

样例

5
1 7
3 10
5 7
4 111
222 12838

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$。