У Ани и Бори есть n кучек с конфетами, причём n чётное число: i-я кучка содержит ai конфет.
Аня любит числа, которые являются квадратами целых чисел, а Боря любит числа, которые не являются квадратами целых чисел. За один ход ребята совместно договариваются выбрать какую-то кучку с конфетами и положить в неё одну новую конфету (которая до этого не лежала ни в одной кучке), либо взять из этой кучки конфету (если эта кучка не пуста), и съесть её.
Определите минимальное количество ходов, необходимых для того, чтобы ровно n / 2 кучек содержали количества конфет, являющиеся квадратами целых чисел, а оставшиеся n / 2 кучек содержали количества конфет, не являющиеся квадратами целых чисел.
Выходные данные
Выведите минимальное количество ходов, необходимых для того, чтобы ровно n / 2 кучек содержали количества конфет, являющиеся квадратами целых чисел, а другие n / 2 кучек содержали количества конфет, не являющиеся квадратами целых чисел. Если для выполнения этих условий не нужно делать ни одного хода, выведите 0.
Примечание
В первом примере достаточно двух ходов. На каждом ходу нужно класть новую конфету во вторую кучку. После этого её размер станет равным 16, поэтому у Ани и Бори станет две кучки, чьи размеры являются квадратами целых чисел (вторая и четвертая кучки), и две кучки, чьи размеры не являются квадратами целых чисел (первая и третья кучки).
Во втором примере необходимо добавить по две конфеты в любые три кучки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
12 14 30 4
|
2
|
|
2
|
6
0 0 0 0 0 0
|
6
|
|
3
|
6
120 110 23 34 25 45
|
3
|
|
4
|
10
121 56 78 81 45 100 1 0 54 78
|
0
|