Решение задачи КУС с Codeforces

Назовем корректным уравнением из спичек (обозначим его как КУС) уравнение вида 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 независимых запросов.