ბესის, როგორც იცით, მოსწონს გახსნილი და დახურული ფრჩხილებისაგან შედგენილი დაბალანსებული სტრიქონები. მას განსაკუთრებით მოსწონს ე.წ. "სუპერდაბალანსებული" სტრიქონები, რომლებიც იწყება გარკვეული რაოდენობის გახსნილი ფრჩხილებით და მთავრდება იგივე რაოდენობის დახურული ფრჩხილებით. მაგალითად ასეთი:

(((())))

ერთ დღეს, ბოსლის მიდამოებში სეირნობისას ბესიმ აღმოაჩინა, რომ ძროხების ნაკვალევი წარმოადგენს N x N ზომის მატრიცას, რომლის თითოეული ელემენტი არის გახსნილი ან დახურული ფრჩხილი. ბესის უნდა, რომ დაიწყოს მატრიცის ზემოთა მარცხენა წერტილიდან და იმოძრაოს ისეთი ტრაექტორიით, რომ მიიღოს მაქსიმალური სიგრძის "სუპერდაბალანსებული" სტრიქონი, ანუ, ჯერ გახსნილი ფრჩხილები, შემდეგ კი იგივე რაოდენობის დახურული ფრჩხილები. დაეხმარეთ მას მაქსიმალური "სუპერდაბალანსებული" სტრიქონის სიგრძის გამოთვლაში.

ყოველ ნაბიჯზე ბესის შეუძლია გადაადგილება ზემოთ, ქვემოთ, მარჯვნივ ან მარცხნივ, თანაც ისე, რომ ერთ ადგილზე ორჯერ არ უნდა მოხვდეს. არ არის გამორიცხული, რომ გარკვეული მატრიცების შემთხვევაში "სუპერდაბალანსებული" სტრიქონი საერთოდაც არ მიიღებოდეს.

შეტანის ფორმატი:

* სტრიქონი 1: ერთი მთელი რიცხვი N (2 <= N <= 5).

* სტრიქონები 2..N+1: თითოეული სტრიქონი შეიცავს N სიგრძის სტრიქონს, რომელიც შედგება გახსნილი და დახურული ფრჩხილებისაგან. ამგვარად მიიღება N x N ზომის მატრიცა, რომლის ელემენტებია გახსნილი და დახურული ფრჩხილები.

გამოტანის ფორმატი:

* სტრიქონი 1: მაქსიმალური "სუპერდაბალანსებული" სტრიქონის სიგრძე. თუ ასეთი სტრიქონი არ შედგება (მაგალითად, თუ ზედა მარცხენა სიმბოლო დახურული ფრჩხილია), გამოტანილი უნდა იქნეს 0.