有 n 个小朋友，每个人都在读一本独一无二的书。在每一天结束时，第 i 个小朋友会把自己的书交给第 p_i 个小朋友（如果 i = p_i，则他把书交给自己）。保证所有 p_i 都是 1 到 n 的不同整数（即 p 是一个排列）。序列 p 在每天都保持不变。

例如，如果 n=6，p=[4, 6, 1, 3, 5, 2]，那么第一天结束时，第 1 个小朋友的书会被第 4 个小朋友拿到，第 2 个小朋友的书会被第 6 个小朋友拿到，依此类推。第二天结束时，第 1 个小朋友的书会被第 3 个小朋友拿到，第 2 个小朋友的书会被第 2 个小朋友拿到，依此类推。

你的任务是，对于每个 i（1 \leq i \leq n），求出第 i 个小朋友的书第一次回到他自己手中的天数。

举个例子：p = [5, 1, 2, 4, 3]。第 1 个小朋友的书会被依次传递给：

- 第一天后，被第 5 个小朋友拿到，

- 第二天后，被第 3 个小朋友拿到，

- 第三天后，被第 2 个小朋友拿到，

- 第四天后，被第 1 个小朋友拿到。

所以，经过四天，第一个小朋友的书会回到他自己手中。第四个小朋友的书会在一天后回到自己手中。

你需要回答 q 个独立的询问。

输入的第一行包含一个整数 q（1 \leq q \leq 1000），表示询问的数量。接下来有 q 个询问。

每个询问的第一行包含一个整数 n（1 \leq n \leq 2 \times 10^5），表示该询问中的小朋友数量。第二行包含 n 个整数 p_1, p_2, \dots, p_n（1 \leq p_i \leq n，所有 p_i 互不相同，即 p 是一个排列），其中 p_i 表示第 i 个小朋友的书会交给第 p_i 个小朋友。

保证所有询问中 n 的总和不超过 2 \times 10^5。

对于每个询问，输出 n 个整数 a_1, a_2, \dots, a_n，其中 a_i 表示在该询问中第 i 个小朋友的书第一次回到他自己手中的天数。

40%的数据：1 \leq n \leq 20;

100%的数据：1 \leq q \leq 1000,1 \leq n \leq 2 \times 10^5,n\times q 2 \times 10^5;