import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class TestsGen {

    final static int MAXN = 1000000;
    final static int NEWLINE_BYTES_LENGTH = 2; // Специально для любителей \10\13 : поставьте 2
    static Random rnd = new Random(3);
    
    final static Matrix f = new Matrix(BigInteger.ONE, BigInteger.ONE, BigInteger.ONE, BigInteger.ZERO);

    static <T> T choice(List<T> list) {
        return list.get(rnd.nextInt(list.size()));
    }
    
    static int tests = 0;
    
    static String print(BigInteger b) {
        int len = b.bitLength();
        if (b.bitLength() > 100) {
            BigInteger mid = BigInteger.TEN.pow(len / 6);
            BigInteger[] res = b.divideAndRemainder(mid);
	    StringBuilder sb = new StringBuilder();
	    sb.append(print(res[0]));
	    String s = print(res[1]);
	    for (int i = 0; i < len / 6 - s.length(); i++)
	    	sb.append('0');
	    sb.append(s);
            return sb.toString();
        } else {
            return b.toString();
        }
    }
    
    static class Matrix {
        final BigInteger a, b, c, d;

        Matrix(BigInteger a, BigInteger b, BigInteger c, BigInteger d) {
            this.a = a;
            this.b = b;
            this.c = c;
            this.d = d;
        }

        Matrix multiply(Matrix m) {
            BigInteger A = a.multiply(m.a).add(b.multiply(m.c));
            BigInteger B = a.multiply(m.b).add(b.multiply(m.d));
            BigInteger D = c.multiply(m.b).add(d.multiply(m.d));
            return new Matrix(A, B, B, D);
        }

        Matrix power(int n) {
            if (n < 2)
                return this;
            else if (n % 2 == 0) {
                Matrix m = power(n / 2);
                return m.multiply(m);
            } else {
                return multiply(power(n - 1));
            }
        }
    }

    static void write(List<BigInteger> list) {
        try {
            tests++;
            PrintWriter out = new PrintWriter(String.format("%02d", tests));
            out.println(list.size());
            for (BigInteger n : list) {
                out.println(print(n));
            }
            out.close();
            System.err.print(String.format("[%02d]", tests));
        } catch (FileNotFoundException e) {
            System.err.println(":(");
            System.exit(1);
        }
    }
    
    static void write(String[] s) {
        try {
            tests++;
            PrintWriter out = new PrintWriter(String.format("%02d", tests));
            out.println(s.length);
            for (String n : s) {
                out.println(n);
            }
            out.close();
            System.err.print(String.format("[%02d]", tests));
        } catch (FileNotFoundException e) {
            System.err.println(":(");
            System.exit(1);
        }
    }
    
    static BigInteger fib(int n) {
        return f.power(n).a;
    }

    static BigInteger transmute(BigInteger b) {
        if (rnd.nextInt(20) == 0) {
            return b.add(BigInteger.ONE);
        }
        if (rnd.nextInt(4) == 0) {
            return b.nextProbablePrime().add(BigInteger.valueOf(rnd.nextInt(100)));
        } else if (rnd.nextInt(3) == 0 && b.bitLength() > 2) {
            return b.add(b).subtract(b.nextProbablePrime());
        } else if (rnd.nextInt(2) == 0 && b.bitLength() > 2) {
            return b.flipBit(b.bitLength());
        } else {
            return b.multiply(BigInteger.valueOf(2));
        }
    }

    static void genRand(int n, List<BigInteger> numbers, double pYes) {
        List<BigInteger> tst = new ArrayList<BigInteger>();
        int remain = n - 10;
        while (true) {
            BigInteger now = choice(numbers);
            if (rnd.nextFloat() > pYes) {
                now = transmute(now);
            }
            if (remain < now.bitLength())
                break;
            tst.add(now);
            remain -= print(now).length() + NEWLINE_BYTES_LENGTH;
        }
        write(tst);
    }

    static void gen(int bits, int cnt) {
        List<BigInteger> numbers = new ArrayList<BigInteger>();
        BigInteger now = BigInteger.ONE;
        for (int i = 1; now.bitLength() < bits - 1; now = fib(i++)) {
            numbers.add(now);
        }
        for (int i = MAXN / cnt; i <= MAXN; i += MAXN / cnt) {
            genRand(i, numbers, .5);
        }

        now = numbers.get(numbers.size() - 1);
        int can = (MAXN - 10) / (NEWLINE_BYTES_LENGTH + now.toString().length());
        now = now.subtract(BigInteger.valueOf(can / 2));
        List<BigInteger> a = new ArrayList<BigInteger>();
        for (int i = 0; i < can; i++) {
            a.add(now);
            now = now.add(BigInteger.ONE);
        }
        write(a);
    }

    static String randStr(int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append((char)('0' + rnd.nextInt(10)));
        }
        return sb.toString();
    }
    
    static void gen1long(int n, double p) {
        List<BigInteger> list = new ArrayList<BigInteger>();
        if (rnd.nextFloat() < p) {
            list.add(fib(rnd.nextInt(n * 5)));
        } else {
            list.add(new BigInteger(randStr(rnd.nextInt(n))));
        }
        write(list);
    }

    static void gen2long(int n, double p) {
        List<BigInteger> list = new ArrayList<BigInteger>();
        boolean b = rnd.nextBoolean();
        for (int i = 0; i < 2; i++) {
        if (b ^ (i == 0)) {
            list.add(fib(rnd.nextInt(n * 5)));
        } else {
            list.add(new BigInteger(randStr(rnd.nextInt(n))));
        }
        }
        write(list);
    }

    static void genSmall() {
	int n = 10;
	for (int j = 0; j < 4; j++) {
        List<BigInteger> list = new ArrayList<BigInteger>();
        	for (int i = 0; i < n; i++) {
            if (rnd.nextFloat() < .5) {
                list.add(fib(rnd.nextInt(20) + 2));
            } else {
                list.add(new BigInteger(randStr((5))));
            }
	}
        write(list);
	n += 2;
	}
    }

    public static void main(String[] args) {
        System.err.println("I'm too lazy for writing FFT. Tests will have been generated slowly...");
        System.err.println("Generating small tests(32bits)...");
	genSmall();
        gen(32, 4);
        int can = (MAXN - 10) / (NEWLINE_BYTES_LENGTH + 1);
        List<BigInteger> list = new ArrayList<BigInteger>();
        for (int i = 0; i < can; i++)
            list.add(BigInteger.ONE);
        write(list);

        System.err.println();
        System.err.println("Generating small tests(64bits)...");
        gen(64, 4);

        System.err.println();
        System.err.println("Yep, it were small tests! Now generating larger tests(but only one number)...");
        for (int i = 500; i <= 7500; i+=500) {
            gen2long(i, .5);
        }

        System.err.println();
        System.err.println("It's time to wail! Relax!");
        list.clear();
        System.err.println("Calculating...");
        BigInteger f = fib(4780000);
        System.err.println("OK!");
        System.err.println("Writing... (Yep, writing a number is slower than it's calculation)");
        list.add(f);
        write(list);
        System.err.println("OK!");

        System.err.println("Again!");
        list.clear();
        list.add(f.add(BigInteger.ONE));
        write(list);

        System.err.println("And again!");
        list.clear();
        list.add(fib(1000000));
        list.add(fib(2000000));
        for (int i = 2; i < 1000; i++) {
            list.add(fib(i));
        }
        write(list);

        System.err.println("And again! [I had already warned you it's slow :) ]");
        list.clear();
        for (int i = 10; i < 2000; i++) {
            f = fib(i);
            list.add(f);
            list.add(f.add(BigInteger.ONE));
        }
        write(list);
        list.clear();
        list.add(fib(123456));
        for (int i = 10; i < 1000; i++) {
            f = fib(i);
            list.add(f);
        }
        f = fib(2000100);
        list.add(f);
        list.add(f.multiply(BigInteger.valueOf(2)));
        write(list);

        System.err.println("Accelerating!!!");
        String[] s = {randStr(MAXN - 10)};
        write(s);
        s = new String[]{randStr(MAXN / 3 - 5), randStr(MAXN / 3 - 5), print(fib(MAXN / 3 * 5))};
        write(s);
        s = new String[(MAXN - 10) / (100 + NEWLINE_BYTES_LENGTH)];
        for (int i = 0; i < s.length; i++)
            s[i] = randStr(100);
	s[rnd.nextInt(s.length)] = print(fib(500));
        write(s);

        System.err.println("And slowdown again...");
        list.clear();
        f = fib(1000);
        int len = print(f).length();
        for (int i = 0; i < (MAXN - 10) / (len + NEWLINE_BYTES_LENGTH); i++)
            list.add(f);
        write(list);

        System.err.println("Finish is so close...");
        s = new String[1400];
        for (int i = 0; i < s.length; i++)
            s[i] = rnd.nextBoolean() ? randStr(i + 1) : print(fib(5 * i + 5));
        write(s);

        for (int i = 0; i < 5; i++)
        {
            list.clear();
            int size = 10;
            BigInteger tmp = fib(1500000 + rnd.nextInt(10 + i * 1000));
            if (rnd.nextBoolean())
        	tmp = tmp.add(new BigInteger(randStr(10000)));
	    size += print(tmp).length();
	    list.add(tmp);
            while (true) {
                BigInteger now = new BigInteger(randStr(20 + 10 * i));
                if (rnd.nextInt(100) == 0)
                    now = fib(92 + 48 * i + rnd.nextInt(5));
                if (size + now.toString().length() + NEWLINE_BYTES_LENGTH > MAXN)
                    break;
                size += now.toString().length() + NEWLINE_BYTES_LENGTH;
                list.add(now);
            }
            write(list);
        }

        for (int i = 0; i < 5; i++) {
            list.clear();
            int size = 10;
            BigInteger tmp = fib(1300000 + rnd.nextInt(100 + i * 100000));
            if (rnd.nextBoolean())
        	tmp = tmp.add(new BigInteger(randStr(100)));
            while (true) {
                BigInteger now = new BigInteger(randStr(20000 + 20000 * i));
                if (rnd.nextInt(10) == 0)
                    now = fib(95700 * (i + 1) + rnd.nextInt(5));
                if (size + now.toString().length() + NEWLINE_BYTES_LENGTH > MAXN)
                    break;
                size += now.toString().length() + NEWLINE_BYTES_LENGTH;
                list.add(now);
            }
            write(list);
        }

    }
}
