Qwerty the Ranger took up a government job and arrived on planet Mars. He should stay in the secret lab and conduct some experiments on bacteria that have funny and abnormal properties. The job isn't difficult, but the salary is high.

At the beginning of the first experiment there is a single bacterium in the test tube. Every second each bacterium in the test tube divides itself into k bacteria. After that some abnormal effects create b more bacteria in the test tube. Thus, if at the beginning of some second the test tube had x bacteria, then at the end of the second it will have kx + b bacteria.

The experiment showed that after n seconds there were exactly z bacteria and the experiment ended at this point.

For the second experiment Qwerty is going to sterilize the test tube and put there t bacteria. He hasn't started the experiment yet but he already wonders, how many seconds he will need to grow at least z bacteria. The ranger thinks that the bacteria will divide by the same rule as in the first experiment. 

Help Qwerty and find the minimum number of seconds needed to get a tube with at least z bacteria in the second experiment.

Input

The first line contains four space-separated integers k, b, n and t (1 ≤ k, b, n, t ≤ 106) — the parameters of bacterial growth, the time Qwerty needed to grow z bacteria in the first experiment and the initial number of bacteria in the second experiment, correspondingly.

Output

Print a single number — the minimum number of seconds Qwerty needs to grow at least z bacteria in the tube.

Examples

Input

3 1 3 5


Output

2

Input

1 4 4 7


Output

3

Input

2 2 4 100


Output

0
#include <bits/stdc++.h>
using namespace std;
template <class F, class T>
T convert(F a, int p = -1) {
  stringstream ss;
  if (p >= 0) ss << fixed << setprecision(p);
  ss << a;
  T r;
  ss >> r;
  return r;
}
template <class T>
T gcd(T a, T b) {
  T r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
template <class T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <class T>
T sqr(T x) {
  return x * x;
}
template <class T>
T cube(T x) {
  return x * x * x;
}
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return s == 0 ? 0 : cntbit(s >> 1) + (s & 1);
}
const long double PI = acos(-1.0);
const long double eps = 1e-9;
const int dr[] = {-1, 0, +1, 0};
const int dc[] = {0, +1, 0, -1};
const int inf = (int)1e9 + 5;
const long long linf = (long long)1e16 + 5;
const long long mod = (long long)1e9 + 7;
class BigInt {
 private:
  char *digits;
  int size;
  int capacity;
  int sign;

 public:
  BigInt(int n, int cap);
  BigInt(int n);
  BigInt(long double d);
  BigInt();
  BigInt(string s);
  BigInt(const char s[]);
  BigInt(const BigInt &n);
  const BigInt &operator=(const BigInt &n);
  const BigInt &operator=(int n);
  ~BigInt();
  void normalize();
  static int sig(int n);
  static int sig(long double n);
  inline int length() { return size; }
  BigInt operator++();
  BigInt operator++(int);
  BigInt operator--();
  BigInt operator--(int);
  BigInt operator-();
  BigInt operator+(int n);
  BigInt operator+(BigInt n);
  BigInt &operator+=(int n);
  BigInt &operator+=(BigInt n);
  BigInt operator-(int n);
  BigInt operator-(BigInt n);
  BigInt &operator-=(int n);
  BigInt &operator-=(BigInt n);
  BigInt operator*(int n);
  BigInt operator*(BigInt n);
  void operator*=(int n);
  void operator*=(BigInt n);
  BigInt operator/(int n);
  BigInt operator/(BigInt n);
  void operator/=(int n);
  void operator/=(BigInt n);
  int operator%(int n);
  BigInt operator%(BigInt n);
  void operator%=(int n);
  void operator%=(BigInt n);
  int divide(int n);
  BigInt divide(BigInt n);
  BigInt operator*(long double n);
  void operator*=(long double n);
  BigInt operator<<(int n);
  void operator<<=(int n);
  BigInt operator>>(int n);
  void operator>>=(int n);
  BigInt operator,(int n);
  BigInt operator,(BigInt n);
  bool operator!();
  operator bool();
  operator string();
  bool operator<(BigInt n);
  bool operator>(BigInt n);
  bool operator==(BigInt n);
  bool operator<=(BigInt n);
  bool operator>=(BigInt n);
  bool operator<(int n);
  bool operator>(int n);
  bool operator==(int n);
  bool operator<=(int n);
  bool operator>=(int n);
  int compare(BigInt n);
  int toInt();
  string toString();
  void print();
  void printWithCommas(ostream &out);

 private:
  void grow();
  friend istream &operator>>(istream &in, BigInt &n);
  friend ostream &operator<<(ostream &out, BigInt n);
  friend long double log2(BigInt x, long double epsilon);
  inline friend long double log(BigInt x, long double epsilon);
  inline friend long double log10(BigInt x, long double epsilon);
  inline friend long double lg(BigInt x, long double epsilon);
  inline friend long double ln(BigInt x, long double epsilon);
};
BigInt operator+(int m, BigInt &n) { return n + m; }
BigInt operator-(int m, BigInt &n) { return -n + m; }
BigInt operator*(int m, BigInt &n) { return n * m; }
BigInt operator/(int m, BigInt &n) { return BigInt(m) / n; }
BigInt operator%(int m, BigInt &n) { return BigInt(m) % n; }
inline bool isDigit(int c) { return (c >= (int)'0' && c <= (int)'9'); }
istream &operator>>(istream &in, BigInt &n) {
  n.size = 0;
  n.sign = 1;
  int sign = 1;
  int c;
  while ((c = in.peek()) >= 0 &&
         (c == ' ' || c == '\t' || c == '\r' || c == '\n'))
    in.get();
  if (c < 0 || (c != (int)'-' && !isDigit(c))) {
    in >> c;
    return in;
  }
  if (c == (int)'-') {
    sign = -1;
    in.get();
  }
  while ((c = in.peek()) >= 0 && isDigit(c)) {
    in.get();
    n *= 10;
    n += (c - (int)'0');
  }
  n.sign = sign;
  n.normalize();
  return in;
}
ostream &operator<<(ostream &out, BigInt n) { return out << n.toString(); }
BigInt::BigInt(int n, int cap) {
  cap = ((cap) > ((int)sizeof(n) * 8) ? (cap) : ((int)sizeof(n) * 8));
  capacity = cap;
  sign = sig(n);
  n *= sign;
  digits = new char[cap];
  memset(digits, 0, cap);
  for (size = 0; n; size++) {
    digits[size] = n % 10;
    n /= 10;
  }
}
BigInt::BigInt(int n) {
  capacity = 1024;
  sign = sig(n);
  n *= sign;
  digits = new char[capacity];
  memset(digits, 0, capacity);
  size = 0;
  while (n) {
    digits[size++] = n % 10;
    n /= 10;
  }
}
BigInt::BigInt(long double d) {
  capacity = 1024;
  sign = (d < 0 ? -1 : d > 0 ? 1 : 0);
  d *= sign;
  digits = new char[capacity];
  memset(digits, 0, capacity);
  size = 0;
  d = floor(d);
  while (d > 0) {
    digits[size++] = (int)((d - floor(d / 10) * 10) + 0.5);
    d = floor(d / 10);
  }
}
BigInt::BigInt() {
  capacity = 128;
  sign = 0;
  digits = new char[capacity];
  memset(digits, 0, capacity);
  size = 0;
}
BigInt::BigInt(string s) {
  capacity = (((int)s.size()) > (16) ? ((int)s.size()) : (16));
  sign = 0;
  digits = new char[capacity];
  memset(digits, 0, capacity);
  istringstream in(s);
  in >> (*this);
}
BigInt::BigInt(const char s[]) {
  capacity = (((int)strlen(s)) > (16) ? ((int)strlen(s)) : (16));
  sign = 0;
  digits = new char[capacity];
  memset(digits, 0, capacity);
  istringstream in(s);
  in >> (*this);
}
BigInt::BigInt(const BigInt &n) {
  capacity = n.capacity;
  sign = n.sign;
  size = n.size;
  digits = new char[capacity];
  memcpy(digits, n.digits, capacity);
}
const BigInt &BigInt::operator=(const BigInt &n) {
  if (&n != this) {
    if (capacity < n.size) {
      capacity = n.capacity;
      delete[] digits;
      digits = new char[capacity];
    }
    sign = n.sign;
    size = n.size;
    memcpy(digits, n.digits, size);
    memset(digits + size, 0, capacity - size);
  }
  return *this;
}
const BigInt &BigInt::operator=(int n) {
  sign = sig(n);
  n *= sign;
  for (size = 0; n; size++) {
    digits[size] = n % 10;
    n /= 10;
  }
  return *this;
}
BigInt::~BigInt() { delete[] digits; }
void BigInt::normalize() {
  while (size && !digits[size - 1]) size--;
  if (!size) sign = 0;
}
int BigInt::sig(int n) { return (n > 0 ? 1 : (n == 0 ? 0 : -1)); }
int BigInt::sig(long double n) { return (n > 0 ? 1 : (n == 0 ? 0 : -1)); }
int BigInt::toInt() {
  int result = 0;
  for (int i = size - 1; i >= 0; i--) {
    result *= 10;
    result += digits[i];
    if (result < 0) return sign * 0x7FFFFFFF;
  }
  return sign * result;
}
string BigInt::toString() {
  string s = (sign >= 0 ? "" : "-");
  for (int i = size - 1; i >= 0; i--) s += (digits[i] + '0');
  if (size == 0) s += '0';
  return s;
}
void BigInt::print() { cout << toString(); }
void BigInt::printWithCommas(ostream &out) {
  if (sign < 0) out.put('-');
  for (int i = size - 1; i >= 0; i--) {
    out.put(digits[i] + '0');
    if (!(i % 3) && i) out.put(',');
  }
  if (size == 0) out.put('0');
}
void BigInt::grow() {
  char *olddigits = digits;
  int oldCap = capacity;
  capacity *= 2;
  digits = new char[capacity];
  memcpy(digits, olddigits, oldCap);
  memset(digits + oldCap, 0, oldCap);
  delete[] olddigits;
}
BigInt BigInt::operator++() {
  operator+=(1);
  return *this;
}
BigInt BigInt::operator++(int) { return operator++(); }
BigInt BigInt::operator--() {
  operator-=(1);
  return *this;
}
BigInt BigInt::operator--(int) { return operator--(); }
BigInt BigInt::operator-() {
  BigInt result(*this);
  result.sign *= -1;
  return result;
}
BigInt BigInt::operator+(int n) {
  BigInt result(*this);
  result += n;
  return result;
}
BigInt BigInt::operator+(BigInt n) {
  BigInt result(*this);
  result += n;
  return result;
}
BigInt &BigInt::operator+=(int n) {
  if (size == capacity) grow();
  int nsign = sig(n);
  if (!nsign) return *this;
  if (!sign) sign = nsign;
  if (sign == nsign) {
    n *= nsign;
    int carry = 0;
    int i;
    for (i = 0; n || carry; i++) {
      int dig = n % 10;
      int newdig = digits[i] + dig + carry;
      digits[i] = newdig % 10;
      carry = newdig / 10;
      n /= 10;
    }
    size = ((i) > (size) ? (i) : (size));
  } else
    operator-=(-n);
  return *this;
}
BigInt &BigInt::operator+=(BigInt n) {
  int maxS = ((size) > (n.size) ? (size) : (n.size)) + 1;
  while (maxS >= capacity) grow();
  if (!n.sign) return *this;
  if (!sign) sign = n.sign;
  if (sign == n.sign) {
    int carry = 0;
    int i;
    for (i = 0; i < maxS - 1 || carry; i++) {
      int newdig = carry;
      if (i < size) newdig += digits[i];
      if (i < n.size) newdig += n.digits[i];
      digits[i] = newdig % 10;
      carry = newdig / 10;
    }
    size = ((i) > (size) ? (i) : (size));
  } else {
    n.sign *= -1;
    operator-=(n);
    n.sign *= -1;
  }
  return *this;
}
BigInt BigInt::operator-(int n) {
  BigInt result(*this);
  result -= n;
  return result;
}
BigInt BigInt::operator-(BigInt n) {
  BigInt result(*this);
  result -= n;
  return result;
}
BigInt &BigInt::operator-=(int n) {
  if (size == capacity) grow();
  int nsign = sig(n);
  if (!nsign) return *this;
  if (!sign) sign = 1;
  if (sign == nsign) {
    BigInt bin = n;
    if (sign >= 0 && *this < bin || sign < 0 && *this > bin) {
      operator=(toInt() - n);
      return *this;
    }
    n *= nsign;
    int carry = 0;
    int i;
    for (i = 0; n || carry; i++) {
      int dig = n % 10;
      int newdig = digits[i] - dig + carry;
      if (newdig < 0)
        newdig += 10, carry = -1;
      else
        carry = 0;
      digits[i] = newdig;
      n /= 10;
    }
    normalize();
  } else
    operator+=(-n);
  return *this;
}
BigInt &BigInt::operator-=(BigInt n) {
  int maxS = ((size) > (n.size) ? (size) : (n.size)) + 1;
  while (maxS >= capacity) grow();
  if (!n.sign) return *this;
  if (!sign) sign = 1;
  if (sign == n.sign) {
    if (sign >= 0 && *this < n || sign < 0 && *this > n) {
      BigInt tmp = n;
      tmp -= *this;
      *this = tmp;
      sign = -sign;
      return *this;
    }
    int carry = 0;
    int i;
    for (i = 0; i < maxS - 1; i++) {
      int newdig = carry;
      if (i < size) newdig += digits[i];
      if (i < n.size) newdig -= n.digits[i];
      if (newdig < 0)
        newdig += 10, carry = -1;
      else
        carry = 0;
      digits[i] = newdig;
    }
    if (carry) {
      if (i) digits[0] = 10 - digits[0];
      size = (i ? 1 : 0);
      for (int j = 1; j < i; j++) {
        digits[j] = 9 - digits[j];
        if (digits[i]) size = j + 1;
      }
      sign *= -1;
    }
    normalize();
  } else {
    n.sign *= -1;
    operator+=(n);
    n.sign *= -1;
  }
  return *this;
}
BigInt BigInt::operator*(int n) {
  BigInt result(0, size + (int)sizeof(n) * 8);
  int nsign = sig(n);
  n *= nsign;
  result.sign = sign * nsign;
  if (!result.sign) return result;
  int i, j;
  for (i = 0; n; i++) {
    int dig = n % 10;
    if (dig) {
      int carry = 0;
      for (j = 0; j < size || carry; j++) {
        int newDig =
            result.digits[i + j] + (j < size ? dig * digits[j] : 0) + carry;
        result.digits[i + j] = newDig % 10;
        carry = newDig / 10;
      }
    }
    n /= 10;
  }
  result.size = i + j - 1;
  return result;
}
BigInt BigInt::operator*(BigInt n) {
  BigInt result(0, size + n.size);
  result.sign = sign * n.sign;
  if (!result.sign) return result;
  int i, j;
  for (i = 0; i < n.size; i++) {
    if (n.digits[i]) {
      int carry = 0;
      for (j = 0; j < size || carry; j++) {
        int newDig = result.digits[i + j] +
                     (j < size ? n.digits[i] * digits[j] : 0) + carry;
        result.digits[i + j] = newDig % 10;
        carry = newDig / 10;
      }
    }
  }
  result.size = i + j - 1;
  return result;
}
void BigInt::operator*=(int n) { operator=(operator*(n)); }
void BigInt::operator*=(BigInt n) { operator=(operator*(n)); }
BigInt BigInt::operator/(int n) {
  if (!n) n /= n;
  BigInt result(*this);
  result /= n;
  return result;
}
BigInt BigInt::operator/(BigInt n) {
  if (!n) n.size /= n.size;
  BigInt result(*this);
  result /= n;
  return result;
}
void BigInt::operator/=(int n) { divide(n); }
void BigInt::operator/=(BigInt n) { divide(n); }
int BigInt::operator%(int n) {
  BigInt tmp(*this);
  return tmp.divide(n);
}
void BigInt::operator%=(int n) { operator=(divide(n)); }
BigInt BigInt::operator%(BigInt n) {
  BigInt tmp(*this);
  return tmp.divide(n);
}
void BigInt::operator%=(BigInt n) { operator=(divide(n)); }
int BigInt::divide(int n) {
  if (!n) n /= n;
  int nsign = sig(n);
  n *= nsign;
  if (!sign) return 0;
  sign *= nsign;
  int tmp = 0;
  for (int i = size - 1; i >= 0; i--) {
    tmp *= 10;
    tmp += digits[i];
    digits[i] = tmp / n;
    tmp -= digits[i] * n;
  }
  normalize();
  return tmp;
}
BigInt BigInt::divide(BigInt n) {
  if (!n) n.size /= n.size;
  if (!sign) return 0;
  sign *= n.sign;
  int oldSign = n.sign;
  n.sign = 1;
  BigInt tmp(0, size);
  for (int i = size - 1; i >= 0; i--) {
    tmp *= 10;
    tmp += digits[i];
    digits[i] = 0;
    while (tmp >= n) {
      tmp -= n;
      digits[i]++;
    }
  }
  normalize();
  n.sign = oldSign;
  return tmp;
}
BigInt BigInt::operator*(long double n) {
  int DIGS_AFTER_DOT = 15;
  int nsign = sig(n);
  n *= nsign;
  int ndigs = n >= 1 ? (int)log10(n) + 1 : 0;
  BigInt result(0, size + ndigs);
  result.sign = sign * nsign;
  if (!result.sign) return result;
  if (n >= 1)
    for (int i = 0; i < ndigs; i++) n /= 10;
  result.size = 0;
  char afterDot[DIGS_AFTER_DOT + 1];
  memset(afterDot, 0, sizeof(afterDot));
  for (int i = ndigs - 1; i >= -DIGS_AFTER_DOT; i--) {
    n *= 10;
    int dig = (int)floor(n);
    n -= dig;
    if (!dig) continue;
    int carry = 0;
    for (int j = 0; j < size || carry; j++) {
      int newdig = (i + j < 0 ? afterDot[-(i + j)] : result.digits[i + j]) +
                   dig * digits[j] + carry;
      (i + j < 0 ? afterDot[-(i + j)] : result.digits[i + j]) = newdig % 10;
      if (i + j >= 0 && result.digits[i + j]) result.size = i + j + 1;
      carry = newdig / 10;
    }
  }
  if (!result.size) result.sign = 0;
  return result;
}
void BigInt::operator*=(long double n) { operator=(operator*(n)); }
BigInt BigInt::operator<<(int n) {
  BigInt result(*this);
  result <<= n;
  return result;
}
void BigInt::operator<<=(int n) {
  if (n < 0)
    operator>>=(-n);
  else if (n > 0) {
    BigInt mult(1, 4 * n);
    for (int i = (1 << 30); i; i >>= 1) {
      mult *= mult;
      if (n & i) mult *= 2;
    }
    operator*=(mult);
  }
}
BigInt BigInt::operator>>(int n) {
  BigInt result(*this);
  result >>= n;
  return result;
}
void BigInt::operator>>=(int n) {
  if (n < 0)
    operator<<=(-n);
  else if (n > 0) {
    BigInt mult(1, 4 * n);
    for (int i = (1 << 30); i; i >>= 1) {
      mult *= mult;
      if (n & i) mult *= 2;
    }
    operator/=(mult);
  }
}
BigInt BigInt::operator,(int n) {
  BigInt result(0, size + (int)sizeof(n) * 8);
  for (result.size = 0; n; result.size++) {
    result.digits[result.size] = n % 10;
    n /= 10;
  }
  memcpy(result.digits + result.size, digits, size * sizeof(digits[0]));
  result.size += size;
  result.sign = 1;
  result.normalize();
  return result;
}
BigInt BigInt::operator,(BigInt n) {
  BigInt result(0, size + n.size);
  memcpy(result.digits, n.digits, n.size * sizeof(n.digits[0]));
  memcpy(result.digits + n.size, digits, size * sizeof(digits[0]));
  result.size = size + n.size;
  result.sign = 1;
  result.normalize();
  return result;
}
bool BigInt::operator!() { return !size; }
BigInt::operator bool() { return size; }
BigInt::operator string() { return toString(); }
bool BigInt::operator<(BigInt n) { return (compare(n) < 0); }
bool BigInt::operator>(BigInt n) { return (compare(n) > 0); }
bool BigInt::operator==(BigInt n) { return (compare(n) == 0); }
bool BigInt::operator<=(BigInt n) { return (compare(n) <= 0); }
bool BigInt::operator>=(BigInt n) { return (compare(n) >= 0); }
bool BigInt::operator<(int n) { return (compare(BigInt(n)) < 0); }
bool BigInt::operator>(int n) { return (compare(BigInt(n)) > 0); }
bool BigInt::operator==(int n) { return (compare(BigInt(n)) == 0); }
bool BigInt::operator<=(int n) { return (compare(BigInt(n)) <= 0); }
bool BigInt::operator>=(int n) { return (compare(BigInt(n)) >= 0); }
int BigInt::compare(BigInt n) {
  if (sign < n.sign) return -1;
  if (sign > n.sign) return 1;
  if (size < n.size) return -sign;
  if (size > n.size) return sign;
  for (int i = size - 1; i >= 0; i--) {
    if (digits[i] < n.digits[i])
      return -sign;
    else if (digits[i] > n.digits[i])
      return sign;
  }
  return 0;
}
long double log2(BigInt x, long double epsilon = 0.000000000000001) {
  static long double O = 0.0;
  if (x.sign <= 0) return O / O;
  long double y = 0.0, z = 1.0, f = 0.0;
  while (x >= 2) {
    if (x.divide(2)) f += 1.0;
    f /= 2.0;
    y++;
  }
  f += 1.0;
  while (z > epsilon) {
    f *= f;
    z /= 2.0;
    if (f >= 2.0) {
      y += z;
      f /= 2.0;
    }
  }
  return y;
}
inline long double log(BigInt x, long double epsilon = 0.000000000000001) {
  return log2(x, epsilon) * 0.6931471805599;
}
inline long double log10(BigInt x, long double epsilon = 0.000000000000001) {
  return log2(x, epsilon) * 0.301029995664;
}
inline long double lg(BigInt x, long double epsilon = 0.000000000000001) {
  return log2(x, epsilon);
}
inline long double ln(BigInt x, long double epsilon = 0.000000000000001) {
  return log(x, epsilon);
}
BigInt powB(BigInt A, int n) {
  BigInt B(1);
  for (int i = (1); i <= (n); ++i) {
    B *= A;
  }
  return B;
}
int sumDigits(BigInt A) {
  int ans = 0;
  string s = A.toString();
  int n = s.size();
  for (int i = (0); i <= (n - 1); ++i) {
    ans += int(s[i]) - int('0');
  }
  return ans;
}
int main() {
  std::ios::sync_with_stdio(false);
  long long k, b, n, t;
  cin >> k >> b >> n >> t;
  if (t == 1) {
    cout << n << '\n';
  } else {
    int ans = n - 1;
    long long A = k, S = 1;
    while (1) {
      if (t < A + b * S) break;
      S += A;
      A *= k;
      ans--;
      if (ans < 0) break;
    }
    cout << ans + 1 << '\n';
  }
  return 0;
}
