Өнөөдөр бяцхан Дашагийн төрсөн өдөр ба тэр 8 нас хүрч байна! Энэ үйл явдалд түүний $n$ ширхэг найз болон хамаатан бүр түүнд дээрээ мэндчилгээтэй тууз өгсөн ба бүх мэндчилгээ ялгаатай. Даша бүх туузыг цуглуулсан ба үлдсэн туузуудыг ганган байлгахаар заримыг нь хаяхаар шийдсэн. Даша ямар ч туузан дээр бичсэн мэндчилгээ өөр туузан дээр бичигдсэн өөр мэндчилгээний дэд тэмдэгт мөр болохгүй байх туузны бүрдлийг ганган гэж үзнэ. $s$-н дэд тэмдэгт мөр гэдэг нь $s$ тэмдэгт мөр дахь үргэлжилсэн хэсгийг хэлнэ.

Дашад бүх найзууддаа гайхуулж чадах боломжит хамгийн олон тууз үлдээхэд туслана уу. Даша туузуудыг эргүүлж, тонгоргож чадахгүй буюу мэндчилгээ бүр оролтонд өгөгдсөн ганц л замаар уншигдана.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 750$) байх Дашагийн хамаатнууд болон найзуудын тоо.

Дараагийн $n$ мөр бүрт яг нэг мэндчилгээ байна. Мэндчилгээ бүр зөвхөн '$a$' болон '$b$' тэмдэгтээс л тогтоно.

Бүх мэндчилгээнүүдийн нийт урт $10 000 000$ тэмдэгтээс хэтрэхгүй.

Гаралт

Эхний мөрөнд ганган бүрдлийн хамгийн их хэмжээг хэвлэ. Хоёр дахь мөрөнд үүнд оролцсон туузнуудын дугааруудыг хэвлэх ба туузнууд оролтонд өгсөн дарааллаараа $1$-c $n$ хүртэл дугаарлагдсан гэж үз. Хэрвээ хамгийн их хэмжээтэй хэд хэдэн ганган бүрдэл байвал алийг нь ч хэвлэж болно.

Жишээн дээр 3 болон 4 туузуудыг хадгалах нь бас зөвд тооцогдоно.