Во время археологической экспедиции группа исследователей нашла в древних руинах n артефактов. Каждый артефакт изначально закреплён за своим археологом: артефакт с номером i принадлежит археологу с номером i.

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

Гарантируется, что массив p является перестановкой чисел от 1 до n. Это означает, что каждый археолог каждый день передаёт ровно один артефакт, и каждый археолог каждый день получает ровно один артефакт.

Для каждого археолога определите, через сколько дней он впервые снова получит свой собственный артефакт.

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

В первой строке содержится одно целое число t — количество наборов входных данных.

Далее следуют описания наборов входных данных.

В первой строке каждого набора содержится целое число n — количество археологов и артефактов.

Во второй строке содержатся n целых чисел p_1, p_2, ..., p_n, где p_i — номер археолога, которому археолог i передаёт артефакт в конце дня.

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

Для каждого набора выведите n чисел.

i-е число должно быть равно количеству дней, через которое археолог i впервые снова получит свой собственный артефакт.

Пример

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

3
5
1 2 3 4 5
6
2 1 4 3 6 5
5
2 3 4 5 1

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

1 1 1 1 1
2 2 2 2 2 2
5 5 5 5 5

Ограничения

• 1 <= t <= 100
• 1 <= n <= 200
• p — перестановка чисел от 1 до n
• сумма n по всем наборам не превосходит 2 * 10^4