У Феникса есть \(n\) монет с весами \(2^1, 2^2, \dots, 2^n\). Он знает, что \(n\) — четное.
Он хочет сложить монеты в две кучки так, что в каждой кучке будет ровно \(\frac{n}{2}\) монет и разница суммарных весов между кучками будет минимальна. Формально, обозначим за \(a\) сумму весов в первой кучке, а за \(b\) — сумму весов во второй. Помогите Фениксу минимизировать \(|a-b|\), то есть модуль числа \(a-b\).
Входные данные состоят из нескольких наборов. В первой строке задано целое число \(t\) (\(1 \le t \le 100\)) — количество наборов входных данных.
В единственной строке каждого набора задано целое число \(n\) (\(2 \le n \le 30\); \(n\) — четное) — количество монет в распоряжении Феникса.
Для каждого набора входных данных выведите единственное целое число — минимально возможную разницу весов между двумя кучками.
В первом наборе входных данных, у Феникса есть две монеты с весами \(2\) и \(4\). Как бы он ни разделил монеты, разница будет равна \(4-2=2\).
Во втором наборе входных данных, у Феникса есть четыре монеты с весами \(2\), \(4\), \(8\) и \(16\). Фениксу выгодно положить монеты с весами \(2\) и \(16\) в одну кучку, а монеты с весами \(4\) и \(8\) — в другую. Разница будет равна \((2+16)-(4+8)=6\).
3 2 3 3 1 3 2 1 3 3 3 1 3
Yes Yes No
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач