E. Автостопом по галактике
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Леша нашел в библиотеке старинную книгу: «Путеводитель для путешествующих автостопом по галактике». В ней рассказывалось, что всего в галактике $$$n$$$ звезд, пронумерованных от $$$0$$$ до $$$n-1$$$, и для каждой звезды $$$i$$$ известно $$$f_i$$$ — звезда, на которую вас готовы подвезти от звезды $$$i$$$.

Леша захотел оценить насколько данный вид путешествий по галактике эффективен. Для этого он посчитал $$$c_i$$$ — количество различных звезд, которые можно посетить, начав путешествие со звезды $$$i$$$. Тогда привлекательностью автостопа назовем сумму $$$c_i$$$ по всем звездам.

Книга была настолько старой, что некоторые числа в ней оказались затерты. У вас есть прекрасная возможность доказать Леше, что автостоп — лучший способ путешествий по галактике: допишите затертые $$$f_i$$$ самостоятельно так, чтобы привлекательность автостопа была максимальна.

Входные данные

В первой строке входного файла содержится одно целое число $$$t$$$ — количество тестов. Каждые следующие две последовательные строки описывают один тест, причем в первой строке содержится одно целое число $$$n$$$. Во второй строке содержатся $$$n$$$ разделенных пробелом целых чисел $$$f_0, f_1, \dots, f_{n-1}$$$. $$$f_i = -1$$$ означает, что звезда, куда вас могут подвезти от звезды $$$i$$$ неизвестна.

$$$$$$1 \le t, n \le 5 \cdot 10^5$$$$$$ $$$$$$-1 \le f_i \le n - 1$$$$$$

Сумма $$$n$$$ по всем тестам не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого теста выведите одну строку содержащую одно число: максимальную привлекательность автостопа.

Пример
Входные данные
2
5
0 1 2 -1 -1
7
-1 -1 -1 -1 -1 -1 -1
Выходные данные
3
42