Белые медведи Меньшиков и Услада из Санкт-Петербургского зоопарка и слоник Хорас из Киевского зоопарка решили построить карточный домик. Для этого они уже нашли внушительную колоду, содержащую n игральных карт. Давайте опишем домик, который они хотят собрать:

1. Домик состоит из некоторого ненулевого количества этажей.
2. Каждый этаж состоит из ненулевого количества комнат и потолка. Комната — две карты, прислоненных друг к другу. Комнаты располагаются в ряд, и на каждые две соседние комнаты кладется потолок из еще одной карты.
3. Каждый этаж, кроме самого нижнего, должен содержать меньше комнат, чем этаж ниже.

Обратите внимание, что домик может заканчиваться этажом с более чем одной комнатой и в таком случае их тоже требуется накрыть потолком. Также количество комнат на соседних этажах не обязательно должно отличаться на единицу, разница может быть больше.

Пока медведи тренируются ставить карты, Хорас пытается сообразить, из скольки этажей должен состоять их дом. Назовем высотой дома количество этажей в нем. Возможно, что из n карт можно собрать много разных домиков разных высот. Кажется, эта задача слонику не под силу, он просит вас посчитать, домики скольки различных высот они смогут собрать, использовав ровно n карт.