Жазғы бағдарламалау мектебінде \(N\) олимпиадшы оқиды, олардың әрқайсысының \(1\)-ден \(N\)-ге дейінгі өзіне тән нөмірі бар. Әр оқушының «крашы» кім екені белгілі — дәл бір басқа қатысушы. Назар аударыңыз, симпатия өзара болуы міндетті емес: егер оқушы \(i\) оқушы \(j\)-ны крашы деп санаса, бұл оқушы \(j\) оқушы \(i\)-ны крашы деп санайды дегенді білдірмейді.

Ұйымдастырушы үстел ойындары бойынша айналмалы турнир өткізуді жоспарлап отыр және кейбір олимпиадшыларды шеңбер бойынша отырғызғысы келеді. Ол мұны әр оқушы шеңберге кіргенде, оның крашы оның жанына — сол жағында немесе оң жағында отыруы үшін жасағысы келеді.

Кейбір қатысушыларды шеңберге отырғызбауға болады — олар тек ойынға бақылаушы болады.

Әр оқушының крашысының шеңберде көршісі (сол жақта немесе оң жақта) болатындай, шеңберге отырғызуға болатын максималды оқушылар санын анықтау қажет.

Енгізу

Бірінші жолда бір бүтін сан \(T\) (\(1 \le T \le 10^4\)) — кіріс деректерінің саны.

Кейінгі жолдарда жинақтардың сипаттамалары беріледі.

Әр жинақтың бірінші жолында бір бүтін сан \(N\) (\(2 \le N \le 10^5\)) — олимпиадшылар саны.

Әр жинақтың екінші жолында \(N\) бүтін сан \(c_1, c_2, \dots, c_N\) жазылған, мұнда \(c_i\) (\(1 \le c_i \le N\), \(c_i \ne i\)) — \(i\)-ші оқушының крашы болып табылатын оқушының нөмірі.

Барлық жинақтар бойынша \(N\) сандарының қосындысы \(10^5\)-тен аспайтынына кепілдік беріледі.

Шығару

Әр кіріс деректері жинағы үшін бір бүтін сан шығарыңыз — шеңбердегі максималды мүмкін оқушылар саны.

Мысалдар

Енгізу 1

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

Жауап 1

3
4
5