永恒地悬停于虚空之中，
闪耀的数据如洪流般涌入祂的脑海。
将过去未来的万物化作符号，
祂于初始之刻推演终末之时。
知识，答案，真相……
信息的迷雾中升腾起璀璨的光，
于是一切对祂都已澄明。

博识尊正在对一个包含 n 个元素的排列 a 尝试新的排序算法。
排列 a 共包含 n 个不同的整数，且所有整数均在 [1,n] 的范围内。

对于排列 a 中的元素，若 a[i]=i ，则认为该编号 i 已经排序完毕，反之是未排序完毕的状态。

每轮排序，博识尊都会按照如下规则，对所有元素进行排序：
1. 找出尚未排序完毕的编号 s[1],s[2],...,s[k] ，其中 s[j]<s[j+1] ；
2. 对于所有 1 到 k 的整数 i ，同时执行修改 a[s[i%k+1]]:=a[s[i]] ；

求 1 到 n 中所有编号 i 分别在第几轮排序后变成排序完毕状态。

第一行输入一个整数 T (1≤T≤10^5) ，表示数据组数。
每组数据第一行包含两个整数 n (1≤n≤10^6) ，表示排列大小。
每组数据第二行包含 n 个整数 a[1],a[2],...,a[n] (1≤a[i]≤n) ，表示排列 a 。

保证所有 n 之和不超过 10^6 。

对于每组数据输出一行包含 n 个整数，其中第 i 个数表示编号 i 在第几轮排序后变成排序完毕状态。

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

1 0 1 1 0 
2 1 2 1 0 1

样例解释
在第一组数据中，
初始编号 2,5 已经是排序完毕状态，对应答案为 0 。
第一轮排序中，编号 1,3,4 是未排序完毕状态，一轮排序后排列 a 变为 [1,2,3,4,5] ，此时编号 1,3,4 变为排序完毕状态，对应答案为 1 。

在第二组数据中，
初始编号 5 已经是排序完毕状态，对应答案为 0 。
第一轮排序中，编号 1,2,3,4,6 是未排序完毕状态，一轮排序后排列 a 变为 [3,2,1,4,5,6] ，此时编号 2,4,6 变为排序完毕状态，对应答案为 1 。
第二轮排序中，编号 1,3 是未排序完毕状态，一轮排序后排列 a 变为 [1,2,3,4,5,6] ，此时编号 1,3 变为排序完毕状态，对应答案为 2 。