Козак Вус вирішив придбати подарунки своїм друзям. Під час подорожі по магазинах він натрапив на дивну акцію: розв'яжи задачу та отримай безкоштовно будь-який товар.
Є n коробок пронумерованих від 1 до n. Вони розташовані по колу, так що коробки i та i+1 сусідні для 1≤i<n. Також коробки 1 та n сусідні. У деяких коробках сховані скарби! Також є запити, які можна робити будь-яку кількість разів.
Опис запиту:
Дізнатися парність сумарної кількості скарбів у трьох будь-яких різних коробках;
Дізнатися парність сумарної кількості скарбів у трьох послідовних коробках.
Козаку Вусу треба знайти наступне:
За яку мінімальну кількість запитів типу (1) можна гарантовано дізнатися, чи кількість скарбів парна чи непарна;
За яку мінімальну кількість запитів типу (2) можна гарантовано дізнатися, чи кількість скарбів парна чи непарна.
Допоможіть Козаку Вусу якнайшвидше розв'язати цю задачу, бо з кожною хвилиною товарів стає все менше!
У вхідних даних знаходяться кілька (не менш одного) тестових випадків.
Перший рядок містить одне ціле число T (1≤T≤105) — кількість тестових випадків.
Кожен з наступних T рядків містить два цілих числа n та t (3≤n≤109,1≤t≤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⋅k, де k — ціле додатне число, то воно буде оцінюватися у 25 балів.
Якщо рішення працює правильно лише при t=1, то воно буде оцінюватися у 25 балів.
Якщо рішення працює правильно лише при t=2, то воно буде оцінюватися у 25 балів.