Zəhmət olmasa, keçin
Hal-hazırda siz dostlarınızla birlikdə xizək sürürsünüz. Ümumilikdə hər şey yaxşı gedir: gündüz xizək sürməkdən zövq alırsınız və əlbəttə ki, gecə də. Lakin bir problem var: xizək lifti. Həmişə olduğu kimi, o çox kiçikdir və hər 5 saniyədə yalnız bir nəfərə xidmət göstərə bilir. Daha da pis olanı, siz və dostlarınız adətən liftdə eyni vaxtda gəlmirsiniz, bu da o deməkdir ki, siz dağın aşağısında lifti gözləyirsiniz və sonra yuxarıda dostlarınızı gözləyirsiniz.
Yuxarıda gözləmək xüsusilə səmərəsizdir. Əslində, başa düşürsünüz ki, əgər dostlarınız hələ gəlməyibsə, başqalarına növbədə sizi keçməyə icazə verə bilərsiniz. Bu sizin üçün fərq etmir, çünki əks halda yuxarıda gözləyəcəksiniz. Digər tərəfdən, əgər dostlarınız artıq gəlib və hazırda onları yuxarıda gözləyirlərsə, bu hərəkətiniz onların vaxtını qənaət edə bilər.
Sizi maraqlandırır ki, əgər hər kəs bu yaxşı davranışları izləsə, nə qədər vaxt qazanılacaq. Siz növbəni diqqətlə izlədiniz və hansı insanların dost qruplarını təşkil etdiyini gördünüz. Tutaq ki, bir insan digərini keçəcək, əgər bu onun öz gözləmə vaxtını dəyişdirməzsə, amma digər insan üçün vaxt qənaət edərsə. Bunu mümkün olduğu qədər təkrar edin. Ümumilikdə nə qədər vaxt qənaət ediləcək?
Giriş məlumatları
Birinci sətir testlərin sayını ehtiva edir, ən çox 100. Sonra hər test üçün:
birinci sətir n (1 ≤ n ≤ 25000) - lift gözləyən insanların sayını ehtiva edir.
ikinci sətir n simvol (böyük və kiçik hərflər və rəqəmlər) ehtiva edir - növbənin təsviri. Sətirdəki birinci insan növbənin başındakı insanı təmsil edir. Eyni simvollar eyni dost qrupuna aid insanları göstərir.
Çıxış məlumatları
Hər test üçün bir sətirdə qənaət edilən vaxtı saniyələrlə göstərin.