You are given a map consisting of N cities. Each city has a directed path to another city or it can be to itself (this means, each city has exactly one outgoing edge).
You are given an array arr. There is a directed path from city i to arr[i] , where 1<=i<=N
You have to start from every city and then travel through cities until you reach a city that you have already visited before.
Task: For each city, determine the number of cities you would visit if you start from that city.
Note: 1-based indexing is followed in the problem.
You have three edges in the graph.
1st edge is from city 1 to city arr that is city 2.
2nd edge is from city 2 to arr that is city 3.
3rd edge is from city 3 to arr that is city 1.
Starting from city1, you visit city 1,2 and 3. There is a path from city 3 to 1, but city 1 is already visited.
Starting from city2, you visit city 2,3 and 1. There is a path from city 1 to 2, but city 2 is already visited.
Starting from city1, you visit city 3,1 and 2. There is a path from city 2 to 3, but city 3 is already visited.
Thus, the answer array is [3,3,3]
First line is T , no of test cases.
For each test case, first line contains a single integer N, no of cities
the second line contains an array arr denoting the array containing the destination city for paths from each city.
For each test case, print N integers acc to problem statement.
1<=arr[i]<=N for all 1<=i<=N
Sum of all N[i] <2x10^5 for all 1<=i<=T
Sample Input 01:
2 4 3 1 4
3 3 1 3 4