Козак Вус та скарби#10258

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

2 секунди

256 мегабайтів

Дуже легка

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

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

Опис запиту:

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

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

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

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

Вхідні дані

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

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

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

Вихідні дані

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

Приклади

Приклад 1

Примітка

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

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

Оцінювання

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

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

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