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

После совещания с правительством города было принято решение построить новую магистраль — скоростной диаметр, который вел бы строго с севера на юг и соединял две точки кольцевой автодороги.

Помимо борьбы с пробками решено было обновить рекорд по протяженности самой длинной магистрали, проложенной с севера на юг. Для того чтобы обновить рекорд необходимо построить магистраль длиной хотя бы \(d\) километров, а поскольку лишних денег в бюджете Флатбурга не так уж и много, решено было построить дорогу длиной ровно \(d\).

Министр транспорта Флатбурга решил предоставить мэру все варианты строительства новой дороги. Для начала он решил подсчитать, сколько существует способов построить магистраль. Помогите министру.

Кальпас — обычный говорящий пес, который живет в зоопарке на Марсе. К сожалению, условия содержания животных там не самые лучшие. Кальпаса выпускают на прогулку только раз в день, да и то, «выпускают» — не самое лучшее слово. Двое охранников: Вася и К-20071027, надевают на Кальпаса специальный ошейник и выводят его во двор. Ошейник полностью контролирует перемещения пса: в любой момент Кальпас находится в точности на середине отрезка между своими охранниками.

К сожалению, тот, кто изобрел этот ошейник, совершенно не думал о собаках. Как любому псу, Кальпасу хочется за время своей прогулки пробежать по строго определенному пути. Как же ему это сделать? Кальпас решил договориться со своими охранниками. Поскольку Вася — робот, который движется каждый день по заданному в его программе маршруту с постоянной скоростью, договориться с ним нет никакой возможности. Единственное, что остается Кальпасу — договориться с К-20071027.

Для того, чтобы подготовиться к переговорам, Кальпас хочет выяснить, путь какой длины должен пройти К-20071027, чтобы Кальпас двигался по намеченному пути с постоянной скоростью.