游侠 Qwerty 接受了一份政府工作并抵达火星。他应该留在秘密实验室,对具有有趣和异常特性的细菌进行一些实验。工作不难,但工资很高。
在第一个实验开始时,试管中有一个细菌。每秒,试管中的每个细菌都会分裂成 k 个细菌。之后,一些异常效应会在试管中产生更多细菌。因此,如果在某一秒开始时试管中有 x 个细菌,那么在第二秒结束时试管将有 kx + b 个细菌。
实验表明,n秒后正好有z个细菌,实验至此结束。
对于第二个实验,Qwerty 将对试管进行消毒并放入细菌。他还没有开始实验,但他已经想知道,他至少需要多少秒才能培养出 z 种细菌。护林员认为细菌会按照与第一个实验相同的规则分裂。
帮助 Qwerty 并找出在第二个实验中获得至少含有 z 个细菌的试管所需的最短秒数。
输入
第一行包含四个空格分隔的整数 k、b、n 和 t (1 ≤ k, b, n, t ≤ 106) — 细菌生长的参数,Qwerty 在第一个实验中生长 z 个细菌所需的时间以及在第二个实验中细菌的初始数量。
输出
打印一个数字 — Qwerty 在试管中生长至少 z 个细菌所需的最短秒数。
示例
输入 #1
3 1 3 5
输出 #1
2
输入 #2
1 4 4 7
输出 #2
3
输入 #3
2 2 4 100
输出 #3
0