Бейбарыс тағы да информатика сабағын ұйықтап қалды! Жаза ретінде мұғалім оған үлкен үй тапсырмасын берді. Үй тапсырмасы келесідей:

Берілген \(s\) жолы. \(f(s)\) функциясын \(s\) жолындағы әрбір символ алдыңғы символға тең емес болатын ең ұзын тізбектік ішкі жолдың ұзындығы ретінде белгілейміз. Мысалы, abbcdgd жолы үшін \(f(s)\) функциясы 4-ке тең болады, яғни abbcdgd ішкі жолы. Ескеріңіз, abbcdgd ішкі жолы жарамсыз, себебі \(s_3\) жолының үшінші символы \(s_2\) жолының алдыңғы символына тең. Тапсырма берілген \(s\) жолы үшін \(f(s)\) мәнін шығару.

Бейбарыс жалқау болғандықтан және мұғалім оған осындай көп тапсырма бергендіктен, ол сізден көмек сұрайды!

Енгізу

Бірінші жолда бір бүтін сан \(t\) (\(1 \le t \le {10}^{3}\)) берілген — үй тапсырмаларының саны.

Әрбір тапсырманың бірінші жолында бір бүтін сан \(n\) (\(1 \le n \le 1000\)) берілген — \(s\) жолының өлшемі.

Әрбір тапсырманың екінші жолында \(s\) жолының өзі беріледі.

Барлық тапсырмалар бойынша \(n\) сандарының қосындысы \(1000\)-нан аспайтынына кепілдік беріледі.

Шығару

Әрбір үй тапсырмасы үшін жеке жолға \(f(s)\) мәнін шығарыңыз.

Мысалдар

Енгізу 1

2
7
abbcdgd
7
abcddge

Жауап 1

4
4