У Феникса есть \(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\).
7 11 3 1 4 1 5 9 2 6 5 3 5 1 1000 3 1 1 1 13 1 2 3 4 5 6 7 8 9 10 11 12 13 2 2 1 6 1 1 1 1 1 1 7 1 1 1 1 1 1 1
6 23 21 1 1000 0 2 1 2 6 45 46 2 2 1 3 4 2 4 4 3
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач