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

Берілген $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