• محدودیت زمان: ۲.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

باباشله‌پز قصد دارد قصر یشم را به آش‌فروشی تبدیل کند! از آنجا که قصر یشم حدود هزار پله دارد او می‌خواهد تا جای ممکن بار کمتری را بر دوش پسرش پو بیندازد. بنابرین تصمیم به فشرده‌سازی آش‌های خود می‌گیرید.

هر آش از تعدادی رشته تشکیل شده‌است و هر رشته نیز دنباله‌ای از حروف کوچک انگلیسی است. حال رشته $B$ را می‌توان به انتهای رشته $A$ وصل کرد اگر حرف آخر $A$ برابر با حرف اول $B$ باشد. توجه کنید طول رشته حاصل از اضافه کردن $B$ به $A$ یکی کمتر از طول مجموعه آن‌ها قبل از اتصال است. مثلاً می‌توانیم ‍amazing را به quera اضافه کنیم تا queramazing به‌دست آید.

طول هر رشته برابر تعداد حروف آن و طول هر آش برابر مجموع طول رشته‌های آن است. پو از شما کمک می‌خواهد.

ورودی

در سطر اول $t$ یا تعداد آش‌ها می‌آید. سپس در خطوط بعد اطلاعات $t$ آش داده می‌شود. $$ 1 \le t \le 100 , 000$$

در سطر اول آش $i$ام $r_i$ یا تعداد رشته‌های آش $i$ام می‌آید. $$ 1 \le |s_{i,j}| \le 1000 , 000$$

سپس در سطر $j$ام از $r_i$ سطر بعد $s_{i,j}$ رشته $j$ام آش $i$ام می‌آید. $$ \sum_{i, j} |s_{i,j}| \le 1000 , 000 $$

خروجی

در $t$ خط کمینه اندازه هر آش پس از فشرده‌سازی را به ترتیب خروجی دهید.

مثال

ورودی نمونه ۱

3
2
shifoo
oogvey
4
quera
math
quantum
amazing
3
abc
cba
a

خروجی نمونه ۱

11
21
5

در آش اول می‌توان oogvey را به انتها shifoo اضافه کرد تا به shifooogvey با طول ۱۱ رسید. راه دیگری برای اتصال آن‌ها نیست و اگر دو رشته از هم جدا باشند هم مجموع طولشان ۱۲ است.

در آش سوم می‌توان ابتدا abc را به انتهای a اضافه کرد تا abc بدست آید و سپس cba را به انتها abc اضافه کرد تا abcba به طول ۵ بدست آید. می‌توان نشان داد آشی با طول کمتر نمی‌توان ساخت.