Problem: The only difference between easy and hard versions is constraints.

There are n kids, each of them is reading a unique book. At the end of any day, the i-th kid will give his book to the p_i-th kid (in case of i = p_i the kid will give his book to himself). It is guaranteed that all values of p_i are distinct integers from 1 to n (i.e. p is a permutation). The sequence p doesn't change from day to day, it is fixed.

For example, if n=6 and p=[4, 6, 1, 3, 5, 2] then at the end of the first day the book of the 1-st kid will belong to the 4-th kid, the 2-nd kid will belong to the 6-th kid and so on. At the end of the second day the book of the 1-st kid will belong to the 3-th kid, the 2-nd kid will belong to the 2-th kid and so on.

Your task is to determine the number of the day the book of the i-th child is returned back to him for the first time for every i from 1 to n.

Consider the following example: p = [5, 1, 2, 4, 3]. The book of the 1-st kid will be passed to the following kids:

  * after the 1-st day it will belong to the 5-th kid, 
  * after the 2-nd day it will belong to the 3-rd kid, 
  * after the 3-rd day it will belong to the 2-nd kid, 
  * after the 4-th day it will belong to the 1-st kid. 



So after the fourth day, the book of the first kid will return to its owner. The book of the fourth kid will return to him for the first time after exactly one day.

You have to answer q independent queries.

Input

The first line of the input contains one integer q (1 ≤ q ≤ 1000) — the number of queries. Then q queries follow.

The first line of the query contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of kids in the query. The second line of the query contains n integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n, all p_i are distinct, i.e. p is a permutation), where p_i is the kid which will get the book of the i-th kid.

It is guaranteed that ∑ n ≤ 2 ⋅ 10^5 (sum of n over all queries does not exceed 2 ⋅ 10^5).

Output

For each query, print the answer on it: n integers a_1, a_2, ..., a_n, where a_i is the number of the day the book of the i-th child is returned back to him for the first time in this query.

Example

Input


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


Output


1 1 1 1 1 
3 3 3 
2 3 3 2 1 3 
1 
2 2 2 2 
4 4 4 1 4 

Solution (in JAVA):

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.StringTokenizer;



public class A {
	static int mx= 200005 ;
//	if(n==1) {
//		System.out.println(1);
//		return;
//	}
//	Arrays.sort(a);
//	Set<Integer> l = new HashSet<>();
//	int c=0;
//	for(int i=0;i<n;i++) {
//		for(int j=n-1;j>i && !l.contains(i);j--) {
//			if(!l.contains(j) && Math.abs((a[j]-a[i]))>1) {
//				c++;
//				l.add(j);
//				l.add(i);
////				System.out.println(a[i]+" "+a[j]);
//				break;
//			}
//		}
//	}
//	System.out.println(c);
	static void solve() throws Exception{
		MScanner sc = new MScanner(System.in);
		int n=s.nextInt();
		int[] a = new int[n+1];
		for(int i=1;i<=n;i++)a[i]=s.nextInt();
		int[] f = new int[n+1];
		Set<Integer> se = new HashSet<>();
		int[] v = new int[n+1];
		Arrays.fill(v, 0);
		for(int i=1;i<=n;i++) {
			int c=1;
			int j=a[i];
			List<Integer> l = new ArrayList<>();
			if(v[i]!=0)continue;
				while(j!=i) {
					l.add(j);
					v[j]=1;
					j=a[j];
					c++;
				}
				l.add(i);
//				System.out.println(l);
				for(int k=0;k<l.size();k++) {
						f[l.get(k)]=c;
					}
				}
		
		for(int i=1;i<=n;i++)System.out.print(f[a[i]]+" ");
		System.out.println();
		
	}
	
	static int gcd(int a,int b) {
		if(a==0)return b;
		return gcd(b%a,a);
	}
	
public static void main(String[] args) throws Exception {
		s = new MScanner(System.in);
		pw = new PrintWriter(System.out);
		int tc = 1;
		
		tc	=s.nextInt();
		for (int test = 1; test <= tc; test++) {
				solve();
		}
		pw.flush();
}
	
	static PrintWriter pw;
	static MScanner s;
	static class MScanner {
		StringTokenizer st;
		BufferedReader br;
		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}
	 	public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}
	 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int[] intArr(int n) throws IOException {
			int[] in = new int[n];
			for (int i = 0; i < n; i++)
				in[i] = nextInt();
			return in;
		}
		public void pArr(int[] in,int n) throws IOException {
			
			for (int i = 0; i < n; i++)
				System.out.println(in[i]);
			
		}
		public void pLis(ArrayList<Integer> l) throws IOException {
			
			for (int i = 0; i < l.size(); i++)
				System.out.println(l.get(i));
			
		}
	 	public long[] longArr(int n) throws IOException {
			long[] in = new long[n];
			for (int i = 0; i < n; i++)
				in[i] = nextLong();
			return in;
		}
		public int[] intSortedArr(int n) throws IOException {
			int[] in = new int[n];
			for (int i = 0; i < n; i++)
				in[i] = nextInt();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}
		public long[] longSortedArr(int n) throws IOException {
			long[] in = new long[n];
			for (int i = 0; i < n; i++)
				in[i] = nextLong();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}
	 	public Integer[] IntegerArr(int n) throws IOException {
			Integer[] in = new Integer[n];
			for (int i = 0; i < n; i++)
				in[i] = nextInt();
			return in;
		}
		public Long[] LongArr(int n) throws IOException {
			Long[] in = new Long[n];
			for (int i = 0; i < n; i++)
				in[i] = nextLong();
			return in;
		}
		public String nextLine() throws IOException {
			return br.readLine();
		}
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}
		public char nextChar() throws IOException {
			return next().charAt(0);
		}
		public long nextLong() throws IOException {
				return Long.parseLong(next());
		}
	 	public boolean ready() throws IOException {
				return br.ready();
		}
		public void waitForInput() throws InterruptedException {
				Thread.sleep(3000);
		}
	}
		static void shuffle(int[] in) {
			for (int i = 0; i < in.length; i++) {
				int idx = (int) (Math.random() * in.length);
				int tmp = in[i];
				in[i] = in[idx];
				in[idx] = tmp;
			}
	}
	 	static void shuffle(long[] in) {
	 		for (int i = 0; i < in.length; i++) {
				int idx = (int) (Math.random() * in.length);
				long tmp = in[i];
				in[i] = in[idx];
				in[idx] = tmp;
			}
		}
}