public class Euler225 {
    static class State {
        int a, b, c;

        State(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        boolean equals(State other) {
            return a == other.a && b == other.b && c == other.c;
        }
    }

    static State next(State s, int n) {
        return new State(s.b, s.c, (s.a + s.b + s.c) % n);
    }

    static boolean dividesTribonacci(int n) {
        State start = new State(1 % n, 1 % n, 1 % n);
        State tortoise = next(start, n);
        State hare = next(next(start, n), n);

        if (tortoise.c == 0 || hare.c == 0)
            return true;

        while (!tortoise.equals(hare)) {
            tortoise = next(tortoise, n);
            hare = next(next(hare, n), n);
            if (tortoise.c == 0 || hare.c == 0)
                return true;
        }

        State cur = new State(tortoise.a, tortoise.b, tortoise.c);
        do {
            if (cur.c == 0)
                return true;
            cur = next(cur, n);
        } while (!cur.equals(tortoise));

        return false;
    }

    public static String solve() {
        int target = 124;
        int found = 0;
        int n = 1;

        while (found < target) {
            n += 2;
            if (!dividesTribonacci(n)) {
                found++;
            }
        }

        return String.valueOf(n);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}