I. Kozak Vus və xəzinələr

Kazak Vus dostlarına hədiyyələr almaq qərarına gəldi. Mağazaları gəzərkən o, maraqlı bir aksiya ilə qarşılaşdı: məsələni həll et və istədiyin məhsulu pulsuz əldə et.

$n$ ədəd qutu var və onlar $1$-dən $n$-ə qədər nömrələnib. Qutular dairəvi şəkildə düzülüb, belə ki, $1\le i<n$ üçün $i$ və $i+1$ qutuları qonşudur. Həmçinin $1$ və $n$ qutuları da qonşudur. Bəzi qutularda xəzinələr gizlənib! İstənilən sayda sorğu etmək mümkündür.

Sorğuların təsviri:

1. İstənilən fərqli üç qutudakı xəzinələrin ümumi sayının cüt və ya tək olduğunu öyrənmək;

2. Ardıcıllıqla üç qutudakı xəzinələrin ümumi sayının cüt və ya tək olduğunu öyrənmək.

Kazak Vus aşağıdakıları tapmalıdır:

1. (1) tipli sorğuların minimum sayında xəzinələrin sayının cüt və ya tək olduğunu necə öyrənmək olar;

2. (2) tipli sorğuların minimum sayında xəzinələrin sayının cüt və ya tək olduğunu necə öyrənmək olar.

Kazak Vusa bu məsələni tez bir zamanda həll etməyə kömək edin, çünki hər dəqiqə məhsullar azalır!

Giriş verilənləri

Giriş məlumatlarında bir neçə (ən azı bir) test halı var.

Birinci sətir bir tam ədəd $T$ ($1\le T\le 10^5$) — test halların sayını ehtiva edir.

Sonrakı $T$ sətirin hər biri iki tam ədəd $n$ və $t$ ($3\le n\le 10^9,1\le t\le 2$) ehtiva edir.

Çıxış verilənləri

$T$ sətir çıxarın. $i$-ci sətir $t$ nömrəli suala $i$-ci test halı üçün cavab olan bir tam ədəd $ans$ ehtiva etməlidir.

Nümunələr

Qeyd

İkinci test halında aşağıdakı sorğuları etmək kifayətdir: $\{1,2,3\}$, $\{2,3,4\}$, $\{3,4,1\}$ və $\{4,1,2\}$.

Üçüncü test halında belə sorğular etmək lazımdır: $\{1,3,5\}$, $\{3,5,4\}$, $\{3,5,2\}$.

Qiymətləndirmə

Əgər həll yalnız $n=3\cdot k$ üçün düzgün işləyirsə, burada $k$ müsbət tam ədəddir, o zaman bu $25$ bal ilə qiymətləndiriləcəkdir.

Əgər həll yalnız $t=1$ üçün düzgün işləyirsə, o zaman bu $25$ bal ilə qiymətləndiriləcəkdir.

Əgər həll yalnız $t=2$ üçün düzgün işləyirsə, o zaman bu $25$ bal ilə qiymətləndiriləcəkdir.