Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem G: cayun日常之拿错伞

Problem G: cayun日常之拿错伞

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 96  Solved: 20
[Submit][Status][Web Board]

Description

cayun cayun cayun cayun cayun cayun大家族

顽皮的搞事cayun 温柔的豆沙cayun

经常做着美梦的 在赏月的cayun

一本正经的芝麻cayun 四个一串

大家 大家 合在一起 就是百人大家族

cayun小宝宝 总是生活在幸福中

cayun老爷爷 慈祥地眯着眼睛

相亲相爱的cayun 手牵手围成一个大大的圆圈

cayun星球上建起家园 大家相视 会心微笑

天上圆圆的月亮里 小兔子在朝着我们挥手

一切开心的和悲伤的事情 全部包含在其中

相亲相爱的cayun 手牵手围成一个大大的圆圈

cayun星球上建起家园 大家相视 会心微笑

天上圆圆的月亮里 小兔子在朝着我们挥手

一切开心的和悲伤的事情 全部包含在其中

啦啦啦啦啦啦啦……

cayun cayun cayun cayun cayun大家族

又到了冬(white)(album)的季节了,虽然cayun们并不冬眠,但受气温影响,智商却在集体下降中,甚至他们经常会拿错东西。比如今天他们上完课好像就拿错了各自的伞,于是之后麻烦就来了,他们想将伞物归原主。由于cayun星球并不盛行货币,所以cayun们之间的交换方式仍是最原始的以伞易伞,也就是说cayunA把手中的伞给了cayunB,那么cayunB也一定要把手中的伞给cayunA。众所周知,cayun们都是懒癌晚期,所以他们想使得交换次数最多的那个cayun的交换次数尽可能少。由于智商下降,cayun们想不出什么好的解决方法,于是只能向大佬星球的你们求助。

Input

第一行一个整数T(T <= 10), 代表数据组数

对于每组数据:

第一行一个整数n(1 <= n <= 100000), 接下来n个正整数(保证为1..n的一个排列), i个数a[i]表示cayun-i开始拿的是cayun-a[i]的东西。

Output

每组数据输出一行,为交换次数最多的cayun的最少交换次数。

Sample Input

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

Sample Output

0
1
2

HINT

[Submit][Status][Web Board]