Яблов и Тостов любят играть. Сегодня они играют со строками по следующим правилам. Сперва Тостов называет Яблову две строки s и t, состоящие исключительно из букв 'A', 'B', 'C', 'D'. Затем Яблов должен как можно быстрее получить строку s. Изначально у него есть пустая строка, за одну секунду он может дописать к концу текущей строки любую непрерывную подстроку строки t.

И вот Тостов и Яблов начинают играть в описанную игру. Тостов уже назвал Яблову строку t, а вот строку s он еще не придумал. Тостов считает, что строка s должна состоять из n символов. Конечно, он хочет придумать самую плохую строку для Яблова (такую, что Яблов проведет как можно больше времени, получая ее). Скажите Тостову, сколько времени Яблов проведет за игрой, если Тостов найдет для него самую худшую строку длины n? Считайте, что Яблов всегда действует оптимально и получает любую строку s за минимально возможное время.