問題文

今から皆さんに、グリッドに関するクイズを出すフッピィ～♪ まずは初級編だピ！

テスターのふっぴーさんは、$N\times N$ のグリッド状の市に住んでいます。 グリッドの各マスは、左上を $(0,0)$ とするようなお名前を持っています。 そこから、$i$ マス下へ、$j$ マス右へ進んだところにあるマスのお名前は、$(i,j)$ です。 マス目に個性をです。これぞダイバーシティーです。（市だけに）

現在の時刻は $0$ です。 テスターのふっぴーさんは、最も左上のマス $(0,0)$ にいます。 テスターのふっぴーさんは、はじめ右を向いています。

ここから毎回「ゲーム終了」まで、時刻の変わり目に移動をするピィ～♪ ルールを説明するピ！

• 一度訪問したマスは二度と訪問してはいけません。
• 四方のいずれにも未訪問のマスがなければ、そこで「ゲーム終了」です。
• 前方（今向いている方向）にマスが存在して、未訪問ならばそこに移動です。
• そうでないならば、前方に未訪問のマスが来るまで、時計回りに回転を繰り返して、未訪問のマスが目の前に来たらそこに移動です。

この一連の移動によって、テスターのふっぴーさんはすべてのマスを訪問して「ゲーム終了」をすることが証明できます。

例を挙げましょう。$N=4$ ならば、このような順番で訪問することになります。

0 1 2 3
11 12 13 4
10 15 14 5
9 8 7 6

さて、問題です（ピィ省略）。テスターのふっぴーさんがマス $(I,J)$ を訪問するのは、時刻がいくつのときでしょうかピ！

入力

$Q$
$N_0{I}_0{J}_0$
$\cdots$
$N_{Q-1}{I}_{Q-1}{J}_{Q-1}$

この問題は、複数テストケースの問題です。 $1$ 行目には、テストケースの数 $Q$ が、一行の整数で入力されます。 $2$ 行目以降の $Q$ 行には、グリッドの一辺の長さ $N_i$、問題のマス目の縦位置 $I_i$、横位置 $J_i$ が空白区切りで与えられます。

制約

• $1\le Q\le 100$
• $1\le N_i\le {10}^9$
• $0\le I_i<N$
• $0\le J_i<N$

出力

$t_0$
$\cdots$
$t_{Q-1}$

サンプル

1
2 1 1

2

0 1
3 2