Vi khuẩn

Trong một ống nghiệm, vi khuẩn phát triển theo quy luật sau: nếu đầu giây nào đó có $x$ vi khuẩn thì cuối giây đó số vi khuẩn trở thành $k·x+b$.

Ở thí nghiệm thứ nhất, ống nghiệm ban đầu chứa $1$ vi khuẩn. Sau đúng $n$ giây, số vi khuẩn đo được là $z$ (không cần tính $z$ trực tiếp).

Ở thí nghiệm thứ hai, ống nghiệm sạch ban đầu được cho vào $t$ vi khuẩn, sinh sản theo cùng quy luật. Hãy tìm số giây nhỏ nhất cần thiết để số vi khuẩn ở thí nghiệm thứ hai lớn hơn hoặc bằng $z$.

Dữ liệu vào

Một dòng duy nhất chứa bốn số nguyên $k$, $b$, $n$, $t$.

Dữ liệu ra

In ra một số nguyên — số giây nhỏ nhất cần thiết ở thí nghiệm thứ hai để có ít nhất $z$ vi khuẩn.

Ràng buộc

• $1\le k,b,n,t\le {10}^6$

Ví dụ