Для своих научных изысканий Рудольф часто штудирует книги по теории графов и находит в них интересные определения: например, недавно он узнал, что неориентированный граф, у которого все вершины имеют равное количество рёбер-соседей, называют регулярным.

Иногда Рудольф вводит собственные термины, если имеющиеся ему чем-то не угодили. Например, ему не понравилось, что понятие регулярности характерно только для неориентированных графов. Кроме того, ограничение, согласно которому из каждой вершины исходит строго одинаковое количество рёбер, показалось ему слишком скучным. Поэтому Рудольф придумал определение квазирегулярного графа.

Ориентированный граф является квазирегулярным, если он обладает следующими свойствами:

1. количество рёбер, исходящих из каждой вершины, либо равно нулю, либо кратно некоторому целому числу k > 1 (разумеется, k постоянно);
2. граф не содержит петель (рёбер, ведущих из вершины в неё же) и кратных рёбер (нескольких рёбер, исходящих из одинаковых вершин и входящих в одинаковые вершины).

Рудольф остался очень доволен своим новым определением и тут же начал рисовать различные квазирегулярные графы. Спустя некоторое время он обратил внимание на то, что некоторые из нарисованных им графов содержали циклы, тогда как другие — нет. Из книг Рудольф знал, что ациклические графы — это очень здорово, поэтому он принялся подробнее изучать (и рисовать) именно ациклические квазирегулярные графы.

Сейчас Рудольф нарисовал на бумаге n точек-вершин. Ему интересно, какое максимальное количество стрелок-рёбер он может дорисовать, чтобы получившийся граф был квазирегулярным и не содержал циклов. Помогите ему найти ответ на этот вопрос.