Назовем корректным уравнением из спичек (обозначим его как КУС) уравнение вида \(a + b = c\), где все числа \(a\), \(b\) и \(c\) целые и больше нуля.
Например, уравнения \(2 + 2 = 4\) (||+||=||||) и \(1 + 2 = 3\) (|+||=|||) являются КУС, а уравнения \(1 + 2 = 4\) (|+||=||||), \(2 + 2 = 3\) (||+||=|||) и \(0 + 1 = 1\) (+|=|) — нет.
У вас есть \(n\) спичек. Вы хотите составить КУС используя все ваши спички. К сожалению, возможно, что у вас не получится составить КУС, используя все ваши спички. Но вы можете докупить несколько спичек и затем собрать КУС!
Например, если \(n = 2\), вы можете купить две спички и составить |+|=||, и если \(n = 5\) вы можете купить одну и составить ||+|=|||.
Посчитайте минимальное количество спичек, которое вам нужно купить для составления КУС.
Обратите внимание, что вам нужно ответить на \(q\) независимых запросов.
Примечание
Первый и второй запросы объяснены в условии.
В третьем запросе вы можете составить \(1 + 3 = 4\) (|+|||=||||), не докупая спичек.
В четвертом запросе вам нужно купить одну спичку и составить \(2 + 4 = 6\) (||+||||=||||||).