I. Козак Вус та скарби

Козак Вус вирішив придбати подарунки своїм друзям. Під час подорожі по магазинах він натрапив на дивну акцію: розв'яжи задачу та отримай безкоштовно будь-який товар.

Є $n$ коробок пронумерованих від $1$ до $n$. Вони розташовані по колу, так що коробки $i$ та $i+1$ сусідні для $1\le i<n$. Також коробки $1$ та $n$ сусідні. У деяких коробках сховані скарби! Також є запити, які можна робити будь-яку кількість разів.

Опис запиту:

1. Дізнатися парність сумарної кількості скарбів у трьох будь-яких різних коробках;

2. Дізнатися парність сумарної кількості скарбів у трьох послідовних коробках.

Козаку Вусу треба знайти наступне:

1. За яку мінімальну кількість запитів типу (1) можна гарантовано дізнатися, чи кількість скарбів парна чи непарна;

2. За яку мінімальну кількість запитів типу (2) можна гарантовано дізнатися, чи кількість скарбів парна чи непарна.

Допоможіть Козаку Вусу якнайшвидше розв'язати цю задачу, бо з кожною хвилиною товарів стає все менше!

Вхідні дані

У вхідних даних знаходяться кілька (не менш одного) тестових випадків.

Перший рядок містить одне ціле число $T$ ($1\le T\le 10^5$) — кількість тестових випадків.

Кожен з наступних $T$ рядків містить два цілих числа $n$ та $t$ ($3\le n\le 10^9,1\le t\le 2$).

Вихідні дані

Виведіть $T$ рядків. $i$-ий рядок повинен містити одне ціле число $ans$, де $ans$ — це відповідь на питання під номером $t$ $i$-го тестового випадку відповідно.

Приклади

Примітка

У другому тестовому випадку достатньо зробити наступні запити: $\{1,2,3\}$, $\{2,3,4\}$, $\{3,4,1\}$ та $\{4,1,2\}$.

У третьому тестовому випадку треба зробити такі запити: $\{1,3,5\}$, $\{3,5,4\}$, $\{3,5,2\}$.

Оцінювання

Якщо рішення працює правильно лише при $n=3\cdot k$, де $k$ — ціле додатне число, то воно буде оцінюватися у $25$ балів.

Якщо рішення працює правильно лише при $t=1$, то воно буде оцінюватися у $25$ балів.

Якщо рішення працює правильно лише при $t=2$, то воно буде оцінюватися у $25$ балів.