#MX165. 最小异或和

最小异或和

题目描述

在一座遥远的王国里,有一位天才机关术士名叫艾尔文。他擅长制造奇特的魔法装置。最近,国王邀请他设计一座“光之塔”,它的核心由一串特殊的魔法水晶排列而成。国王只给了艾尔文两个数字:nn 和 xx。

艾尔文的任务是选择恰好 nn 块水晶,每块水晶都刻有一个正整数编号。魔法塔的核心要求是:这 nn 块水晶在激活后,编号通过异能共鸣运算(即异或,记作 ⊕)的总结果必须等于 xx。

作为一个追求完美的工匠,艾尔文不满足于随意拼凑。他决定在所有满足条件的水晶排列中,选出一组总编号和最小的方案。虽然他最终并没有把排列写下来(因为那实在太长),但他将这组方案的元素总和作为献给国王的答案。

输入格式

每个测试包含多个测试用例。

第一行包含测试用例的数量 tt (1≤t≤1041 \leq t \leq 10^4)。接下来是测试用例的描述。

每个测试用例由包含一对数字 nn 和 xx(1≤n≤1091 \leq n \leq 10^9,0≤x≤1090 \leq x \leq 10^9)的单行组成 —— 这是国王给的数字。

输出格式

对于每个测试用例,输出艾尔文给国王的方案 —— 满足所有条件的元素之和。如果不存在合适的方案,输出 -1。

样例

样例输入 1

3
10 1
2 3
10 10

样例输出 1

13
3
18

样例输入 2

1
5 2

样例输出 2

6

数据范围与约定

数据点编号 特殊性质
1∼31 \sim 3 1≤t≤3,1≤n,x≤101 \leq t \leq 3, 1 \leq n,x \leq 10
4∼64 \sim 6 t=1t = 1
7∼107 \sim 10 无

对于 100%100\% 的数据,满足:

  • 1≤t≤1041 \leq t \leq 10^4
  • 1≤n,x≤1091 \leq n, x \leq 10^9