Задано n куль, з них n – 1 куля має однакову вагу, а одна важча. Потрібно за мінімальну кількість зважувань на шалькови терезах визначити, яка з куль є важчою. Операція зважування полягає у тому, що на кожну із двох шальок терезів кладеться одинаковв кількість куль. Якщо якась шалька переважила — важку кулю покладено серед тих, що знаходяться у ній. Якщо терези виявились у рівновазі — важка куля серед тих, що не лежать на терезах. Після кожного зважування можна прийняти рішення про те, які кульки будуть приймати участь у наступному зважуванні.
Одне ціле число n (2 ≤ n ≤ 10^9
).
Вивести мінімальну кількість зважувань, необхідну для гарантованого виявлення важкої кулі.