問題文

正整数 $N$ と非負整数 $M$ が与えられます。

$N$ 頂点の重み付き完全グラフ $G$ の各頂点には $0$ から $N - 1$ の番号がついており、任意の $0 \leq a < b < N$ について、頂点 $a$ と頂点 $b$ を結ぶ辺の重みは $(a + M) \oplus (b + M)$ です。ここで、$\oplus$ はビットごとの排他的論理和を表します。

$G$ の最小全域木の辺の重みの和を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて解いてください。

制約

• $1\leq T\leq 10^{5}$
• $1\leq N\leq 2\times 10^{9}$
• $0\leq M\leq 2\times 10^{9}$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられます。

$T$
$case_{1}$
$case_{2}$
$\vdots$
$case_{T}$

各ケースは以下の形式で与えられます。

$N$ $M$

出力

$T$ 行出力してください。

$i$ 行目には $case_{i}$ に対する答えを出力してください。

サンプル

3
3 2
167 924
1234567890 1234567890

7
2551
21772702017