### 问题描述 小辉有一个无限长的数组 $A$ ，这个数组很有特点，对于第 $i$ 个元素 $a_i$ ： - 如果 $i=2^k$ ， $k$ 为自然数，那么 $a_i=-i$ 。 - 如果 $i=2^k$ ， $k$ 为自然数，那么 $a_i=i$ 。 小坤想和小辉玩一个游戏，小坤给出一对 $l,r(l\leq r)$ ，小辉计算出 $\sum_{i=l}^r a_i$ 。但是小辉算的太慢了，他请聪明的你帮忙写一段代码来实现。 ### 输入格式 第一行一个数字 $q$ 代表小坤的询问次数。 接下来 $q$ 行，第 $i$ 行两个数字 $l_i,r_i$ 表示小坤询问的区间。 ### 输出格式 输出 $q$ 行，每行一个数字表示询问结果。 ### 样例输入 ```text 7 1 2 1 3 3 8 1 100 4 5 1 4 8 989 ``` ### 样例输出 ```text -3 0 9 4796 1 -4 487495 ``` ### 说明 当 $l=1,r=2$ 时，答案为 $-1-2=-3$ 。 ### 评测数据规模 对于 $100$% 的评测数据， $1\leq q\leq 10^5,1\leq l_i\leq r_i \leq 10^9$ 。