Давайте назвемо масив [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
У першому тестовому випадку масив уже є хорошим, оскільки і добуток, і сума дорівнюють .
У другому тестовому випадку спочатку добуток дорівнює 6. Ми можемо додати до цього масиву, він стане [3, 2, 1], а добуток і сума дорівнюватимуть .
У третьому тестовому випадку ми можемо додати і до нашого масиву, він стане [1, 1, -1, 2, 1, 1, -2, 1] із сумою та добутком дорівнює .
У четвертому тестовому випадку масив [-1, 0, 1] уже є хорошим, і добуток, і сума дорівнюють .
У п’ятому тестовому випадку ви можете додати до нашого масиву, він перетвориться на [1, -1, 2, -1, 1, 1, 3], і сума, і добуток дорівнюватимуть .