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$ баллов.