Зрівняти#12887

Зрівняти

1 секунда
256 мегабайтів
Складна

Давайте назвемо масив [b_1, b_2, \ldots, b_m] хороший, якщо b_1\cdot b_2 \cdot \ldots \cdot b_m = b_1 + b_2 + \ldots + b_m.

Вам надано масив a_1, a_2, \ldots, a_n. За одну операцію ви можете додати будь-який цілий елемент до цього масиву. Яку найменшу кількість операцій потрібно виконати, щоб зробити його хорошим?

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 5\cdot 10^4)  — кількість тестів. Нижче наведено опис тестових випадків.

Перший рядок кожного тесту містить одне ціле число (1 \le n \le 2\cdot 10^5)  — довжина масиву.

Другий рядок кожного тесту містить цілих чисел a_1, a_2, \ldots, a_n (-10^6 \le a_i \le 10^6)  — елементи масиву.

Гарантується, що сума за всіма тестами не перевищує 2\cdot 10^5.

Вихідні дані

Для кожного тесту виведіть єдине ціле число  — найменшу кількість операцій, які вам потрібно зробити, щоб зробити масив хорошим.

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку масив уже є хорошим, оскільки і добуток, і сума дорівнюють .

У другому тестовому випадку спочатку добуток дорівнює 6. Ми можемо додати до цього масиву, він стане [3, 2, 1], а добуток і сума дорівнюватимуть .

У третьому тестовому випадку ми можемо додати і до нашого масиву, він стане [1, 1, -1, 2, 1, 1, -2, 1] із сумою та добутком дорівнює .

У четвертому тестовому випадку масив [-1, 0, 1] уже є хорошим, і добуток, і сума дорівнюють .

У п’ятому тестовому випадку ви можете додати до нашого масиву, він перетвориться на [1, -1, 2, -1, 1, 1, 3], і сума, і добуток дорівнюватимуть .