[THE SxPLAY & KIVΛ - 漂流](https://soundcloud.com/kivawu/hyouryu)

[KIVΛ & Nikki Simmons - Perspectives](https://soundcloud.com/kivawu/perspectives)

With a new body, our idol Aroma White (or should we call her Kaori Minamiya?) begins to uncover her lost past through the OS space.

The space can be considered a 2D plane, with an infinite number of data nodes, indexed from 0, with their coordinates defined as follows:

  * The coordinates of the 0-th node is (x_0, y_0) 
  * For i > 0, the coordinates of i-th node is (a_x ⋅ x_{i-1} + b_x, a_y ⋅ y_{i-1} + b_y) 



Initially Aroma stands at the point (x_s, y_s). She can stay in OS space for at most t seconds, because after this time she has to warp back to the real world. She doesn't need to return to the entry point (x_s, y_s) to warp home.

While within the OS space, Aroma can do the following actions:

  * From the point (x, y), Aroma can move to one of the following points: (x-1, y), (x+1, y), (x, y-1) or (x, y+1). This action requires 1 second. 
  * If there is a data node at where Aroma is staying, she can collect it. We can assume this action costs 0 seconds. Of course, each data node can be collected at most once. 



Aroma wants to collect as many data as possible before warping back. Can you help her in calculating the maximum number of data nodes she could collect within t seconds?

Input

The first line contains integers x_0, y_0, a_x, a_y, b_x, b_y (1 ≤ x_0, y_0 ≤ 10^{16}, 2 ≤ a_x, a_y ≤ 100, 0 ≤ b_x, b_y ≤ 10^{16}), which define the coordinates of the data nodes.

The second line contains integers x_s, y_s, t (1 ≤ x_s, y_s, t ≤ 10^{16}) – the initial Aroma's coordinates and the amount of time available.

Output

Print a single integer — the maximum number of data nodes Aroma can collect within t seconds.

Examples

Input


1 1 2 3 1 0
2 4 20


Output


3

Input


1 1 2 3 1 0
15 27 26


Output


2

Input


1 1 2 3 1 0
2 2 1


Output


0

Note

In all three examples, the coordinates of the first 5 data nodes are (1, 1), (3, 3), (7, 9), (15, 27) and (31, 81) (remember that nodes are numbered from 0).

In the first example, the optimal route to collect 3 nodes is as follows: 

  * Go to the coordinates (3, 3) and collect the 1-st node. This takes |3 - 2| + |3 - 4| = 2 seconds. 
  * Go to the coordinates (1, 1) and collect the 0-th node. This takes |1 - 3| + |1 - 3| = 4 seconds. 
  * Go to the coordinates (7, 9) and collect the 2-nd node. This takes |7 - 1| + |9 - 1| = 14 seconds. 



In the second example, the optimal route to collect 2 nodes is as follows: 

  * Collect the 3-rd node. This requires no seconds. 
  * Go to the coordinates (7, 9) and collect the 2-th node. This takes |15 - 7| + |27 - 9| = 26 seconds. 



In the third example, Aroma can't collect any nodes. She should have taken proper rest instead of rushing into the OS space like that.
#include <bits/stdc++.h>
using namespace std;
vector<set<pair<long long, long long>>> coprime(200001);
void prime_factorization() {
  for (long long i = 2; i <= 200000; i += 2) {
    long long cnt = 0, t = i;
    while (t % 2 == 0) {
      t /= 2;
      cnt++;
    }
    coprime[i].insert({cnt, 2});
  }
  for (long long i = 3; i <= 200000; i += 3) {
    long long cnt = 0, t = i;
    while (t % 3 == 0) {
      t /= 3;
      cnt++;
    }
    coprime[i].insert({cnt, 3});
  }
  for (long long i = 5; i <= 200000; i += 6) {
    if (coprime[i].size() == 0) {
      for (long long j = i; j <= 200000; j += i) {
        long long cnt = 0, t = j;
        while (t % i == 0) {
          t /= i;
          cnt++;
        }
        coprime[j].insert({cnt, i});
      }
    }
    if (coprime[i + 2].size() == 0) {
      for (long long j = i + 2; j <= 200000; j += i + 2) {
        long long cnt = 0, t = j;
        while (t % (i + 2) == 0) {
          t /= (i + 2);
          cnt++;
        }
        coprime[j].insert({cnt, i + 2});
      }
    }
  }
}
bool isprime(long long n) {
  if (n < 2) return false;
  if (n == 2 || n == 3) return true;
  if (n % 2 == 0) return false;
  if (n % 3 == 0) return false;
  for (long long i = 5; i <= sqrt(n); i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }
  return true;
}
void swap(long long &a, long long &b) {
  long long temp = a;
  a = b;
  b = temp;
}
long long power(long long a, long long n) {
  if (a == 0) return 0;
  long long res = 1;
  while (n) {
    if (n % 2) {
      res = (res * a);
      n--;
    } else {
      a = (a * a);
      n /= 2;
    }
  }
  return res;
}
long long bin_power(long long a, long long n) {
  if (a == 0) return 0;
  long long res = 1;
  while (n) {
    if (n % 2) {
      res = (res * a) % 1000000007;
      n--;
    } else {
      a = (a * a) % 1000000007;
      n /= 2;
    }
  }
  return res;
}
void p_factors(long long &n, map<long long, long long> &m) {
  if (n % 2 == 0) {
    long long c = 0;
    while (n % 2 == 0) {
      n /= 2;
      c++;
    }
    m[2] = c;
  }
  for (long long i = 3; i <= sqrt(n); i += 2) {
    if (n % i == 0) {
      long long c = 0;
      while (n % i == 0) {
        n /= i;
        c++;
      }
      m[i] = c;
    }
  }
  if (n != 1) m[n] = 1;
}
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long extended_gcd(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0;
    *y = 1;
    return b;
  }
  long long x1, y1;
  long long g = extended_gcd(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return g;
}
void simple_sieve(long long n, vector<long long> &primes) {
  if (n < 2) return;
  if (n < 3) {
    primes.push_back(2);
    return;
  }
  vector<bool> mark(n + 1, true);
  mark[2] = true;
  mark[3] = true;
  primes.push_back(2);
  primes.push_back(3);
  for (long long i = 5; i * i < n; i += 6) {
    if (mark[i]) {
      for (long long j = i * i; j < n; j += i) mark[j] = false;
    }
    if (mark[i + 2] && (i + 2) < sqrt(n)) {
      for (long long j = (i + 2) * (i + 2); j < n; j += (i + 2))
        mark[j] = false;
    }
  }
  for (long long i = 5; i < n; i += 6) {
    if (mark[i]) primes.push_back(i);
    if (mark[i + 2] && (i + 2) < n) primes.push_back(i + 2);
  }
}
vector<long long> linear_sieve(long long n) {
  vector<long long> primes;
  if (n < 2) return primes;
  if (n < 3) {
    primes.push_back(2);
    return primes;
  }
  vector<long long> mark(n + 1);
  for (long long i = 2; i <= n; i++) {
    if (mark[i] == 0) {
      primes.push_back(i);
      mark[i] = i;
    }
    for (long long j = 0;
         j < primes.size() && primes[j] <= mark[i] && i * primes[j] <= n; j++)
      mark[i * primes[j]] = primes[j];
  }
  return primes;
}
void segmented_sieve(long long n, vector<long long> &primes) {
  if (n < 2) return;
  long long limit = sqrt(n) + 1;
  simple_sieve(limit, primes);
  long long low = limit;
  long long high = 2 * limit;
  while (low < n) {
    if (high >= n) high = n + 1;
    vector<bool> mark(high - low + 2, true);
    for (long long i = 0; i < primes.size(); i++) {
      long long lolim = (low / primes[i]) * primes[i];
      if (lolim < low) lolim += primes[i];
      for (long long j = lolim; j < high; j += primes[i]) mark[j - low] = false;
    }
    for (long long j = low; j < high; j++) {
      if (mark[j - low]) primes.push_back(j);
    }
    low += limit;
    high += limit;
  }
}
void ranged_primes(long long low, long long high, vector<long long> &primes) {
  if (low < 2) low = 2;
  if (high < 2) return;
  long long lim = sqrt(high);
  vector<long long> pr = linear_sieve(lim);
  if (pr.size() == 0) {
    if (high == 2) {
      primes.push_back(2);
      return;
    }
    if (high == 3) {
      if (low <= 2) {
        primes.push_back(2);
        primes.push_back(3);
        return;
      }
      primes.push_back(3);
      return;
    }
  }
  vector<bool> mark(high - low + 1, true);
  for (auto &i : pr) {
    long long j = i * i;
    if (j < low) {
      j = (low / i) * i;
      if (j < low) j += i;
    }
    while (j <= high) {
      mark[j - low] = false;
      j += i;
    }
  }
  for (long long i = low; i <= high; i++) {
    if (mark[i - low]) primes.push_back(i);
  }
}
long long totient(long long n) {
  long long res = n;
  for (long long i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        n /= i;
      }
      res -= res / i;
    }
  }
  if (n > 1) res -= res / n;
  return res;
}
void phi_1_to_n(long long n, vector<long long> &phi) {
  for (long long i = 0; i <= n; i++) {
    phi[i] = i;
  }
  for (long long i = 2; i <= n; i++) {
    if (phi[i] == i) {
      for (long long j = i; j <= n; j += i) {
        phi[j] -= phi[j] / i;
      }
    }
  }
}
long long factorial(long long n) {
  long long res = 1;
  for (long long i = 2; i <= n; i++) {
    res = (res * i) % 1000000007;
  }
  return res % 1000000007;
}
long long sumofint(long long n) {
  string s = to_string(n);
  long long sum = 0;
  for (long long i = 0; i < s.size(); i++) {
    int j = s[i];
    j -= 48;
    sum += j;
  }
  return sum;
}
long long modinverse(long long n) { return bin_power(n, 1000000007 - 2); }
long long ncr(long long n, long long r) {
  if (n < 0 || r > n || r < 0) return 0;
  if (n - r < r) r = n - r;
  vector<long long> c(n + 1);
  c[0] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = min(i, r); j > 0; j--) {
      c[j] = (c[j] + c[j - 1]) % 1000000007;
    }
  }
  return c[r] % 1000000007;
}
long long lcs(string &a, string &b, long long m, long long n, long long &l1,
              long long &l2) {
  vector<vector<long long>> L(n, vector<long long>(m));
  long long i, j, flag = 0;
  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      if (a[i - 1] == b[j - 1]) {
        L[i][j] = L[i - 1][j - 1] + 1;
      } else
        L[i][j] = max(L[i - 1][j], L[i][j - 1]);
    }
  }
  return L[m][n];
}
bool issorted(vector<long long> &v, long long n) {
  for (long long i = 1; i < n; i++) {
    if (v[i] < v[i - 1]) return false;
  }
  return true;
}
string bin_string(long long n, long long l) {
  string s;
  for (long long i = l - 1; i >= 0; i--) {
    if (n % 2)
      s.push_back('1');
    else
      s.push_back('0');
    n /= 2;
  }
  reverse(s.begin(), s.end());
  return s;
}
bool ispel(string s) {
  long long b = 0, e = s.size() - 1;
  while (s[b] == s[e] && b < e) {
    b++;
    e--;
  }
  if (b >= e) return true;
  return false;
}
class dsu {
  long long n, c;
  vector<long long> parent, size;

 public:
  dsu(long long x) {
    n = x;
    c = 0;
    vector<long long> v(x + 1), s(x + 1, -1);
    for (long long i = 1; i <= x; i++) {
      v[i] = i;
      s[i] = 1;
    }
    parent = v;
    size = s;
  }
  void create(long long v) {
    parent[v] = v;
    size[v] = 1;
  }
  void unite(long long a, long long b) {
    long long x = find(a);
    long long y = find(b);
    if (x != y) {
      if (size[x] < size[y]) swap(x, y);
      parent[y] = x;
      size[x] += size[y];
      size[y] = 0;
    } else
      c++;
  }
  long long find(long long a) {
    if (parent[a] == a) return a;
    return parent[a] = find(parent[a]);
  }
  void finish() {
    for (long long i = 1; i <= n; i++) {
      parent[i] = find(i);
    }
  }
  bool iscycle(long long x, long long y) {
    long long a = find(x);
    long long b = find(y);
    if (a == b) return true;
    return false;
  }
  long long cycle() { return c; }
  long long connect() {
    long long cnt = 0;
    for (long long i = 1; i <= n; i++) {
      if (size[i]) cnt++;
    }
    return cnt;
  }
  map<long long, vector<long long>> group() {
    map<long long, vector<long long>> mp;
    for (long long i = 1; i <= n; i++) {
      mp[parent[i]].push_back(i);
    }
    return mp;
  }
};
vector<long long> dsu_set(vector<vector<long long>> &g, long long n) {
  long long c = -1;
  queue<long long> q;
  vector<long long> mark(n + 1), p(n + 1);
  for (long long i = 1; i <= n; i++) {
    if (mark[i]) continue;
    c++;
    q.push(i);
    mark[i] = 1;
    p[i] = c;
    while (!q.empty()) {
      long long f = q.front();
      q.pop();
      for (long long x : g[f]) {
        if (mark[x]) continue;
        q.push(x);
        mark[x] = 1;
        p[x] = c;
      }
    }
    return p;
  }
}
class graph {
  long long n, m, timer, res;
  vector<vector<long long>> g;
  vector<long long> mark, in, out, d, p, low, clr, sub, lev;
  queue<long long> ar;
  queue<long long> q;
  vector<pair<long long, long long>> e;

 public:
  graph(long long x, long long y) {
    n = x;
    m = y;
    g.resize(n + 1);
  }
  void create() {
    for (long long i = 0; i < m; i++) {
      long long x, y;
      cin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
      e.push_back({x, y});
    }
  }
  bool bip(long long v, long long c) {
    mark[v] = 1;
    clr[v] = c;
    for (long long x : g[v]) {
      if (mark[x]) {
        if (clr[x] == 1 - clr[v]) continue;
        return false;
      }
      if (bip(x, 1 - clr[v]) == false) return false;
    }
    return true;
  }
  bool isbip() {
    mark.assign(n + 1, 0);
    clr.assign(n + 1, -1);
    for (long long i = 1; i <= n; i++) {
      if (mark[i]) continue;
      if (bip(i, 0) == false) return false;
    }
    return true;
  }
  void show() {
    for (long long i = 1; i <= n; i++) {
      cout << i << " -> ";
      for (long long x : g[i]) {
        cout << x << " ";
      }
      cout << endl;
    }
  }
  void inout() {
    timer = 0;
    mark.assign(n + 1, 0);
    in.assign(n + 1, 0);
    out.assign(n + 1, 0);
    for (long long i = 1; i <= n; i++) {
      if (mark[i]) continue;
      into(i);
    }
  }
  void into(long long v) {
    mark[v] = 1;
    in[v] = ++timer;
    for (long long x : g[v]) {
      if (mark[x]) continue;
      into(x);
    }
    out[v] = timer++;
  }
  bool cycle() {
    p.assign(n + 1, 0);
    mark.assign(n + 1, 0);
    for (long long i = 1; i <= n; i++) {
      if (mark[i]) continue;
      mark[i] = 1;
      q.push(i);
      while (!q.empty()) {
        long long f = q.front();
        q.pop();
        for (long long x : g[f]) {
          if (mark[x]) {
            if (x != p[f]) {
              return true;
            }
            continue;
          }
          mark[x] = 1;
          q.push(x);
          p[x] = f;
        }
      }
    }
    return false;
  }
  long long diameter() {
    mark.assign(n + 1, 0);
    long long mx = 0, ind = 1;
    dist(1, 0, mx, ind);
    mx = 0;
    long long idx = 1;
    mark.assign(n + 1, 0);
    dist(ind, 0, mx, idx);
    return mx;
  }
  void dist(long long v, long long dt, long long &mx, long long &ind) {
    mark[v] = 1;
    if (dt > mx) {
      mx = dt;
      ind = v;
    }
    for (long long x : g[v]) {
      if (mark[x]) continue;
      dist(x, dt + 1, mx, ind);
    }
  }
  void subtree() {
    mark.assign(n + 1, 0);
    sub.assign(n + 1, 0);
    subt(1);
  }
  void subt(long long v) {
    mark[v] = 1;
    sub[v] = 1;
    for (long long x : g[v]) {
      if (mark[x]) continue;
      subt(x);
      sub[v] += sub[x];
    }
  }
  vector<long long> distance(long long x) {
    mark.assign(n + 1, 0);
    d.assign(n + 1, 0);
    p.assign(n + 1, 0);
    d[0] = 1;
    q.push(x);
    mark[x] = 1;
    while (!q.empty()) {
      long long f = q.front();
      q.pop();
      for (long long y : g[f]) {
        if (mark[y]) continue;
        mark[y] = 1;
        q.push(y);
        p[y] = p[f] + 1;
        ++d[p[f] + 1];
      }
    }
    return d;
  }
  bool isbridge() {
    mark.assign(n + 1, 0);
    in.assign(n + 1, -1);
    low.assign(n + 1, -1);
    timer = 0;
    return bdg(1, -1);
  }
  bool bdg(long long v, long long p) {
    mark[v] = 1;
    in[v] = low[v] = ++timer;
    for (long long x : g[v]) {
      if (x == p) continue;
      if (mark[x]) {
        low[v] = min(low[v], in[x]);
      } else {
        bool res = bdg(x, v);
        if (res == true) return res;
        low[v] = min(low[v], low[x]);
        if (low[x] > in[v]) return true;
      }
    }
    return false;
  }
  queue<long long> art() {
    mark.assign(n + 1, 0);
    in.assign(n + 1, 0);
    low.assign(n + 1, 0);
    timer = 0;
    for (long long i = 1; i <= n; i++) {
      if (!mark[i]) {
        arti(i);
      }
    }
    return ar;
  }
  void arti(long long v, long long p = -1) {
    mark[v] = 1;
    in[v] = low[v] = ++timer;
    long long child = 0;
    for (long long x : g[v]) {
      if (x == p) continue;
      if (mark[x]) {
        low[v] = min(low[v], in[x]);
      } else {
        arti(x, v);
        low[v] = min(low[v], low[x]);
        if (low[x] >= in[v] && p != -1) {
          ar.push(v);
        }
        child++;
      }
    }
    if (p == -1 && child > 1) ar.push(v);
  }
  void solve(long long k) {
    subtree();
    lev.assign(n + 1, 0);
    clr.assign(n + 1, 0);
    dfs(1, 1);
    long long ans = 0;
    for (long long i = 1; i <= n; i++) {
      cout << lev[i] << " " << sub[i] << endl;
      sub[i] -= lev[i];
    }
    sort(sub.begin(), sub.end());
    for (long long i = k + 1; i <= n; i++) ans += sub[i];
    cout << ans;
  }
  void dfs(long long v, long long l) {
    clr[v] = 1;
    lev[v] = l;
    for (long long x : g[v]) {
      if (clr[x]) continue;
      dfs(x, l + 1);
    }
  }
};
long long root(long long n) {
  long long i = 0;
  while (i * i <= n) {
    i++;
  }
  return i - 1;
}
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long tc = 1;
  while (tc--) {
    long long x0, y0, ax, bx, ay, by, x, y, t, ans = 0, n = -1;
    cin >> x0 >> y0 >> ax >> ay >> bx >> by;
    cin >> x >> y >> t;
    vector<pair<long long, long long>> p;
    p.push_back({x0, y0});
    for (long long i = 1; i <= 80; i++) {
      p.push_back({ax * p[i - 1].first + bx, ay * p[i - 1].second + by});
      if (p[i].first < p[i - 1].first || p[i].second < p[i - 1].second) {
        n = p.size() - 2;
        break;
      }
    }
    for (long long i = 0; i <= n; i++) {
      long long cnt = 0, a = x, b = y, ctr = 0;
      for (long long j = i; j >= 0; j--) {
        long long temp = cnt + abs(a - p[j].first) + abs(b - p[j].second);
        if (temp < cnt) break;
        cnt = temp;
        a = p[j].first;
        b = p[j].second;
        if (cnt > t) break;
        ctr++;
      }
      if (cnt < t) {
        for (long long j = i + 1; j <= n; j++) {
          long long temp = cnt + abs(a - p[j].first) + abs(b - p[j].second);
          if (temp < cnt) break;
          cnt = temp;
          a = p[j].first;
          b = p[j].second;
          if (cnt > t) break;
          ctr++;
        }
      }
      ans = max(ans, ctr);
    }
    cout << ans << endl;
  }
  return 0;
}
