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

где m — это общее количество песен, а a и b — числа от 0 до m − 1. Сгенерированная последовательность номеров должна удовлетворять следующим правилам:

• x₀ … x_{m − 1} должны являться перестановкой чисел от 0 до m − 1,
• x_m должно быть равно нулю.

Саша захотел вычислить все пары значений (a_i, b_i), дающие требуемые последовательности, и вычислить среднее арифметическое среди всех чисел a_i в этих парах. Помогите ему!

Входные данные состоят не более чем из 100 тестов. Каждый тест представляет собой единственное целое число m (1 < m < 10⁹), записанное в отдельной строке.

Выведите для каждого теста в отдельной строке среднее арифметическое чисел a_i, округлённое вниз.