Космічна Станція
Молоді програмісти Петро та Станку були найняті двома космічними агентствами. Агентство Петра побудувало станцію, що складається з модулів. Деякі пари модулів з'єднані коридорами так, що можна дістатися з кожного модуля до будь-якого іншого унікальним шляхом через коридори. Немає жодного коридору, який починається і закінчується в одному модулі, а також немає двох або більше коридорів, що з'єднують одні й ті ж два модулі. Зовнішні модулі з'єднані рівно з одним іншим модулем (білі на малюнку) і пронумеровані від 1 до N. Вони лише для розваги. Все обладнання станції зосереджено у внутрішніх модулях — з'єднаних з більш ніж одним іншим модулем (чорні на малюнку). Керівники Петра хотіли б зберегти в таємниці кількість внутрішніх модулів. Щоб приховати кількість внутрішніх модулів, Петро закодував топологію станції, вказавши для кожної пари зовнішніх модулів відстань між ними (тобто кількість коридорів на унікальному шляху між модулями).
Тепер у Станку складне завдання — він пообіцяв своїм начальникам розшифрувати кодування Петра і знайти кількість внутрішніх модулів станції. На жаль, він недостатньо досвідчений. Допоможіть йому. Напишіть програму для вирішення цього завдання.
Вхідні дані
На першому рядку вхідного файлу буде вказано число T тестових випадків. Кожен тестовий випадок починається з рядка, що містить число N зовнішніх модулів (3 ≤ N ≤ 1024). Потім слідують N – 1 рядків. На першому з цих рядків вказані відстані від зовнішнього модуля 1 до зовнішніх модулів 2, 3,…, N, розділені одним пробілом. На другому рядку вказані, також розділені одним пробілом, відстані від зовнішнього модуля 2 до зовнішніх модулів 3, 4, …, N, і так далі. Останній рядок містить лише відстань від зовнішнього модуля N – 1 до зовнішнього модуля N.
Вихідні дані
Для кожного тестового випадку програма повинна вивести на окремому рядку стандартного виходу число M внутрішніх модулів станції. У всіх тестових випадках M буде менше 1024.