@Override
    public Long solve() {

        final Rational[][][] cache = new Rational[9][10][];
        
        for (int len = 1; len <= 9; ++len) {
            for (int first = 0, last; (last = first + len) <= 9; ++first) {

                final Set<Rational> tmp = new TreeSet<Rational>();
                
                for (int m = first + 1; m < last; ++m) {
                    for (Rational left : cache[first][m]) {
                        for (Rational right : cache[m][last]) {
                            if (right.num != 0) {
                                tmp.add(left.add(right));
                                tmp.add(left.subtract(right));
                                tmp.add(left.multiply(right));
                                tmp.add(left.divide(right));
                            } else {
                                tmp.add(left);
                                tmp.add(right);
                            }
                        }
                    }
                }
                tmp.add(concat(first, last));
                cache[first][last] = tmp.toArray(new Rational[tmp.size()]);
            }
        }
        
        long sum = 0;
        
        for (Rational r : cache[0][9]) {
            if (r.num > 0 && r.num % r.den == 0) sum += r.num / r.den;
        }

        return sum;
    }