問題文

$2^{60}-1$ 行 $60$ 列のグリッドがあり、以下のように各行が行番号の二進数表記に合わせて白黒で塗り分けられています。
行番号 $x$、列番号 $y$ のマス $(x,y)$ は $x$ の二進数表記における $2^y$ の位が $1$ のとき黒マス、$0$ のとき白マスとなります。

ここでは黒マス $(x, y)$ を含む連結成分とは、$(x, y)$ から上下左右に隣接している黒マスのみを移動して到達できる黒マス全体の集合のことです。
黒マス $(x, y)$ を含む連結成分に属する黒マスの個数を $T$ 個のテストケースについて求めてください。

入力

$T$
$case_1$
$case_2$
$\vdots$
$case_T$ 

$x\ y$ 

• $1 \le T \le 10^5$
• $1 \le x < 2^{60}$
• $0 \le y < 60$
• $(x, y)$ は黒マスである。つまり、$x$ の二進数表記における $2^y$ の位は $1$ である。

出力

標準出力に $T$ 行で出力してください。$i$ 行目（$i \leq T$）には、$i$ 個目のテストケースに対する答えを出力してください。最後に改行してください。

サンプル

2
2 1
7 0

3
7