A. О микробах
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Взявшись за очередное правительственное задание, рейнджер Йцукен прибыл на планету Марс. В стенах секретной лаборатории рейнджеру нужно провести несколько опытов над бактериями, обладающими странными аномальными свойствами. Работа несложная, но за нее обещали хорошо заплатить.

В начале первого опыта в пробирке находится одна бактерия. Каждую секунду каждая из бактерий в пробирке делится на k бактерий, после чего, в силу аномальных эффектов, в пробирке материализуются еще b бактерий. Таким образом, если в начале какой-либо секунды было x бактерий, то к концу этой секунды становится kx + b бактерий.

Как показал опыт, через n секунд бактерий стало ровно z, и на этом эксперимент завершился.

В ходе второго опыта пробирка будет продезинфицирована, после чего туда будет помещено t бактерий. Йцукен еще не начал проводить опыт, но ему уже интересно, через сколько секунд бактерий станет не меньше, чем z? Рейнджер считает, что бактерии будут делиться по такому же правилу, как и в первом опыте.

Помогите Йцукену, найдите наименьшее количество секунд, через которое количество бактерий во втором опыте станет не меньше, чем z.

Входные данные

В первой строке через пробел записаны четыре целых числа k, b, n и t (1 ≤ k, b, n, t ≤ 106) — параметры размножения бактерий, время, через которое в пробирке оказалось z бактерий в первом опыте, и начальное количество бактерий во втором опыте, соответственно.

Выходные данные

Выведите одно число — наименьшее количество секунд, через которое бактерий станет не меньше, чем z.

Примеры
Входные данные
3 1 3 5
Выходные данные
2
Входные данные
1 4 4 7
Выходные данные
3
Входные данные
2 2 4 100
Выходные данные
0