В далекой-далекой галактике n обитаемых планет, пронумерованных числами от 1 до n. Они расположены на огромных расстояниях друг от друга, поэтому сообщение между ними было крайне затруднено, пока на планете с номером 1 не был изобретен гипердвигатель. Как только произошло это знаменательное событие, на планете 1 был построен n - 1 космический корабль, и эти корабли были разосланы на остальные планеты, чтобы сообщить о революционном изобретении.

Гиперпространство, как это ни парадоксально, представляет собой обычное трехмерное евклидово пространство. Обитаемые планеты можно считать неподвижными точками в нем, причем никакие две точки не совпадают и никакие три точки не лежат на одной прямой. Движение корабля, оснащенного гипердвигателем, между двумя планетами осуществляется по прямой с постоянной скоростью, одинаковой для всех кораблей. Поэтому расстояния в гиперпространстве измеряются в гипергодах (корабль, оснащенный гипердвигателем, преодолевает расстояние в s гипергодов за s лет).

Когда корабль прилетает на обитаемую планету, жители планеты разбирают его, создают по его образу и подобию n - 2 корабля с гипердвигателем и рассылают их на остальные n - 2 планеты (кроме той, с которой прилетел корабль). Время создания новых кораблей по сравнению со временем их движения от одной планеты к другой настолько мало, что им можно пренебречь. Новые корабли абсолютно идентичны разосланным первоначально: они движутся с той же постоянной скоростью по прямолинейной траектории и, прибывая на планету, выполняют ту же миссию, т.е. их разбирают, строят новые n - 2 корабля и рассылают их на все планеты, кроме той, с которой прилетел корабль. Таким образом, процесс распространения важной новости по галактике продолжается.

Однако создатели гипердвигателя так торопились распространить известие о своем открытии, что не изучили до конца, что происходит при столкновении двух кораблей в гиперпространстве. Если два движущихся корабля оказываются в одной точке, то происходит взрыв колоссальной силы, приводящий к уничтожению галактики!

Ваша задача — вычислить время жизни галактики с момента запуска кораблей с первой планеты.