Никиту привлекает всё нестандартное. Даже десятичная система ему больше не нравится, так что он решил изучить другие системы счисления. Его внимание привлекла система счисления с основанием b. Для начала её изучения он хочет записать в свой блокнот все числа длины n без ведущих нулей в этой системе счисления. На каждом листе бумаги в его блокноте достаточно места для написания ровно c чисел. Никита записывает каждое подходящее число ровно один раз, начиная с первого чистого листа бумаги и не оставляя на листах свободного места. Никита никогда не выпишет число 0, так как с ним у него связаны плохие воспоминания о делении чисел.
Помогите Никите выяснить, сколько чисел будет записано на последнем листе бумаги.
Выходные данные
В единственной строке выходных данных выведите количество чисел, записанных на том листе бумаги, на котором будет записано последнее число.
Примечание
В обоих примерах существует ровно 4 числа длины 3 в двоичной системе счисления. В первом примере Никита запишет 3 числа на первом листе бумаги и 1 число на втором. Во втором примере все 4 числа поместятся на один лист бумаги.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3 3
|
1
|
|
2
|
2 3 4
|
4
|