[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.
    import java.io.ByteArrayInputStream;
    import java.io.IOException;
    import java.io.InputStream;
    import java.io.PrintWriter;
    import java.util.*;
    import java.io.*;
    import java.math.*;
    public class Main {
        InputStream is;
        PrintWriter out;
        String INPUT = "";
        //class  Declaration

        static class pair implements Comparable < pair > {
            long x;
            long y;


            pair(long i, long j) {
                x = i;
                y = j;


            }
            public int compareTo(pair p) {
                if (this.x != p.x) {
                    return Long.compare(this.x,p.x);
                } else {
                    return Long.compare(this.y,p.y);
                }
            }
            public int hashCode() {
                return (x + " " + y).hashCode();
            }
            public String toString() {
                return x + " " + y;
            }
            public boolean equals(Object o) {
                pair x = (pair) o;
                return (x.x == this.x && x.y == this.y);
            }
        }
        // int[] dx = {0,0,1,-1};
        // int[] dy = {1,-1,0,0};
        // int[] ddx = {0,0,1,-1,1,-1,1,-1}; 
        // int[] ddy = {1,-1,0,0,1,-1,-1,1};

    int inf = (int) 1e9 + 9;
    long biginf  = (long)1e17 + 7 ;
    long mod =  (int)1e9 + 7;  
   

    void solve() throws Exception {
       long[] points = new long[6];
       for(int i=0;i<6;++i) points[i]=nl();
       long[] initial = new long[3];
       for(int i=0;i<3;++i) initial[i]=nl();

       pair sit = new pair(initial[0],initial[1]);
       ArrayList<pair> path  =new ArrayList<>();
       pair start = new pair(points[0],points[1]);
       path.add(start);
     
       while(true){
      
           try{
                start = new pair( Math.addExact(Math.multiplyExact(points[2],start.x) ,points[4]), Math.addExact(Math.multiplyExact(points[3],start.y) ,points[5]));
           }
           catch(ArithmeticException e){
            break ;
           }
           if(euclidean_dist(sit,start)<= initial[2]) path.add(start);
        
        
       }
     //  pn(path);
       long ans = 0 ;
       for(int i=0;i<path.size();++i){
            long cnt = 0;
            pair source = sit ;
            long dist =  0;
            for(int j=i;j<path.size();++j){
                try{
                    dist  = Math.addExact(dist,euclidean_dist(source,path.get(j)));
                }
                catch(ArithmeticException e){
                    dist = Long.MAX_VALUE;
                }

                if(dist <= initial[2]){
                    cnt++;

                }
                else{
                    break ;

                }
                source = path.get(j);
            }
            ans = Math.max(ans,cnt);
        }

        for(int i=path.size()-1;i>=0;--i){
            long cnt = 0;
            pair source = sit ;
            long dist =  0;
            for(int j=i;j>=0;--j){
                try{
                    dist  = Math.addExact(dist,euclidean_dist(source,path.get(j)));
                }
                catch(ArithmeticException e){
                    dist = Long.MAX_VALUE;
                }

                if(dist <= initial[2]){
                    cnt++;

                }
                else{
                    break ;

                }
                source = path.get(j);
            }
            ans = Math.max(ans,cnt);
        }

        pn(ans);

        

    }
    long euclidean_dist(pair p1,pair p2){
       long ans = Long.MAX_VALUE ;
        try{ 
        ans = Math.addExact(Math.abs(p1.x-p2.x) ,Math.abs(p2.y-p1.y));
        }
        catch(ArithmeticException e){

        }
        return ans ;
    }
 


        long pow(long a, long b) {
            long result = 1;
            while (b > 0) {
                if (b % 2 == 1) result = (result * a) % mod;
                b /= 2;
                a = (a * a) % mod;
            }
            return result;
        }


        void print(Object o) {
            System.out.println(o);
            System.out.flush();
        }



        long gcd(long a, long b) {
            if (b == 0)
                return a;
            return gcd(b, a % b);
        }
        void run() throws Exception {
            is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
            out = new PrintWriter(System.out);

            long s = System.currentTimeMillis();
            solve();
            out.flush();
            if (!INPUT.isEmpty()) tr(System.currentTimeMillis() - s + "ms");
        }


        public static void main(String[] args) throws Exception {
            new Main().run();
        }

        //output methods
        private void pn(Object o) {
            out.println(o);
        }
        private void p(Object o) {
            out.print(o);
        }
        private ArrayList < ArrayList < Integer >> ng(int n, int e) {
            ArrayList < ArrayList < Integer >> g = new ArrayList < > ();
            for (int i = 0; i <= n; ++i) g.add(new ArrayList < > ());

            for (int i = 0; i < e; ++i) {
                int u = ni(), v = ni();
                g.get(u).add(v);
                g.get(v).add(u);
            }

            return g;
        }

        private ArrayList < ArrayList < pair >> nwg(int n, int e) {
            ArrayList < ArrayList < pair >> g = new ArrayList < > ();
            for (int i = 0; i <= n; ++i) g.add(new ArrayList < > ());

            for (int i = 0; i < e; ++i) {
                int u = ni(), v = ni(), w = ni();
                g.get(u).add(new pair(w, v));
                g.get(v).add(new pair(w, u));
            }

            return g;
        }


        //input methods
        private byte[] inbuf = new byte[1024];
        public int lenbuf = 0, ptrbuf = 0;


        private int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }




        private boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        private int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b));
            return b;
        }

        private double nd() {
            return Double.parseDouble(ns());
        }
        private char nc() {
            return (char) skip();
        }

        private String ns() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        private char[] ns(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        private char[][] nm(int n, int m) {
            char[][] map = new char[n][];
            for (int i = 0; i < n; i++) map[i] = ns(m);
            return map;
        }

        private int[] na(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

        private int ni() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        private long nl() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        private void tr(Object...o) {
            if (INPUT.length() > 0) System.out.println(Arrays.deepToString(o));
        }
        void watch(Object...a) throws Exception {
            int i = 1;
            print("watch starts :");
            for (Object o: a) {
                //print(o);
                boolean notfound = true;
                if (o.getClass().isArray()) {

                    String type = o.getClass().getName().toString();
                    //print("type is "+type);
                    switch (type) {
                        case "[I":
                            {
                                int[] test = (int[]) o;
                                print(i + " " + Arrays.toString(test));
                                break;
                            }
                        case "[[I":
                            {
                                int[][] obj = (int[][]) o;

                                print(i + " " + Arrays.deepToString(obj));
                                break;
                            }
                        case "[J":
                            {

                                long[] obj = (long[]) o;
                                print(i + " " + Arrays.toString(obj));
                                break;
                            }
                        case "[[J":
                            {

                                long[][] obj = (long[][]) o;
                                print(i + " " + Arrays.deepToString(obj));
                                break;
                            }
                        case "[D":
                            {

                                double[] obj = (double[]) o;
                                print(i + " " + Arrays.toString(obj));
                                break;
                            }
                        case "[[D":
                            {

                                double[][] obj = (double[][]) o;
                                print(i + " " + Arrays.deepToString(obj));
                                break;
                            }
                        case "[Ljava.lang.String":
                            {

                                String[] obj = (String[]) o;
                                print(i + " " + Arrays.toString(obj));
                                break;
                            }
                        case "[[Ljava.lang.String":
                            {

                                String[][] obj = (String[][]) o;
                                print(i + " " + Arrays.deepToString(obj));
                                break;
                            }
                        case "[C":
                            {
                                char[] obj = (char[]) o;
                                print(i + " " + Arrays.toString(obj));
                                break;
                            }
                        case "[[C":
                            {

                                char[][] obj = (char[][]) o;
                                print(i + " " + Arrays.deepToString(obj));
                                break;
                            }



                        default:
                            {
                                print(i + " type not identified");
                                break;
                            }
                    }
                    notfound = false;

                }
                if (o.getClass() == ArrayList.class) {
                    print(i + " al: " + o);
                    notfound = false;
                }
                if (o.getClass() == HashSet.class) {
                    print(i + " hs: " + o);
                    notfound = false;
                }
                if (o.getClass() == TreeSet.class) {
                    print(i + " ts: " + o);
                    notfound = false;
                }
                if (o.getClass() == TreeMap.class) {
                    print(i + " tm: " + o);
                    notfound = false;
                }
                if (o.getClass() == HashMap.class) {
                    print(i + " hm: " + o);
                    notfound = false;
                }
                if (o.getClass() == LinkedList.class) {
                    print(i + " ll: " + o);
                    notfound = false;
                }
                if (o.getClass() == PriorityQueue.class) {
                    print(i + " pq : " + o);
                    notfound = false;
                }
                if (o.getClass() == pair.class) {
                    print(i + " pq : " + o);
                    notfound = false;
                }

                if (notfound) {
                    print(i + " unknown: " + o);
                }
                i++;
            }
            print("watch ends ");
        }

    }