Козак Вус вирішив придбати подарунки своїм друзям. Під час подорожі по магазинах він натрапив на дивну акцію: розв'яжи задачу та отримай безкоштовно будь-який товар. Є $n$ коробок пронумерованих від $1$ до $n$. Вони розташовані по колу, так що коробки $i$ та $i+1$ сусідні для $1 \le i < n$. Також коробки $1$ та $n$ сусідні. У деяких коробках сховані скарби! Також є запити, які можна робити будь-яку кількість разів. Опис запиту: \begin{enumerate} \item Дізнатися парність сумарної кількості скарбів у трьох \textbf{будь-яких різних} коробках; \item Дізнатися парність сумарної кількості скарбів у трьох \textbf{послідовних} коробках. \end{enumerate} Козаку Вусу треба знайти наступне: \begin{enumerate} \item За яку \textbf{мінімальну} кількість запитів типу (1) можна гарантовано дізнатися, чи кількість скарбів парна чи непарна; \item За яку \textbf{мінімальну} кількість запитів типу (2) можна гарантовано дізнатися, чи кількість скарбів парна чи непарна. \end{enumerate} Допоможіть Козаку Вусу якнайшвидше розв'язати цю задачу, бо з кожною хвилиною товарів стає все менше! \InputFile У вхідних даних знаходяться кілька (не менш одного) тестових випадків. Перший рядок містить одне ціле число $T$ ($ 1 \le T \le 10^5 $) --- кількість тестових випадків. Кожен з наступних $T$ рядків містить два цілих числа $n$ та $t$ ($3 \le n \le 10^9, 1 \le t \le 2$). \OutputFile Виведіть $T$ рядків. $i$-ий рядок повинен містити одне ціле число $ans$, де $ans$ --- це відповідь на питання під номером $t$ $i$-го тестового випадку відповідно. \Note У другому тестовому випадку достатньо зробити наступні запити: $\{1, 2, 3\}$, $\{2, 3, 4\}$, $\{3, 4, 1\}$ та $\{4, 1, 2\}$. У третьому тестовому випадку треба зробити такі запити: $\{1, 3, 5\}$, $\{3, 5, 4\}$, $\{3, 5, 2\}$. \Scoring Якщо рішення працює правильно лише при $n=3 \cdot k$, де $k$ --- ціле додатне число, то воно буде оцінюватися у $25$ балів. Якщо рішення працює правильно лише при $t=1$, то воно буде оцінюватися у $25$ балів. Якщо рішення працює правильно лише при $t=2$, то воно буде оцінюватися у $25$ балів.