Problem: Spongebob is already tired trying to reason his weird actions and calculations, so he simply asked you to find all pairs of n and m, such that there are exactly x distinct squares in the table consisting of n rows and m columns. For example, in a 3 × 5 table there are 15 squares with side one, 8 squares with side two and 3 squares with side three. The total number of distinct squares in a 3 × 5 table is 15 + 8 + 3 = 26.

Input

The first line of the input contains a single integer x (1 ≤ x ≤ 1018) — the number of squares inside the tables Spongebob is interested in.

Output

First print a single integer k — the number of tables with exactly x distinct squares inside.

Then print k pairs of integers describing the tables. Print the pairs in the order of increasing n, and in case of equality — in the order of increasing m.

Examples

Input

26


Output

6
1 26
2 9
3 5
5 3
9 2
26 1


Input

2


Output

2
1 2
2 1


Input

8


Output

4
1 8
2 3
3 2
8 1

Note

In a 1 × 2 table there are 2 1 × 1 squares. So, 2 distinct squares in total.

<image>

In a 2 × 3 table there are 6 1 × 1 squares and 2 2 × 2 squares. That is equal to 8 squares in total.

<image>

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class CodeForces {
    
    static long i, j;
    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        long n = Reader.nextLong() * 6;
        ArrayList<String> a = new ArrayList();
        ArrayList<String> b = new ArrayList();
      
        for(long i = 1; i < 7000000; i++){
            if((n+i*i*i-i) %(i+1) != 0)
                continue;
           long x = n+i*i*i-i;
           x /= i+1;
           
           if(x % (3*i) != 0)
               continue;
           
           x /= 3*i;
           
           if(x < i)
               break;
           
           a.add(i + " " + x);
           if(i != x)
               b.add(x + " " + i);
        }
        
        
        System.out.println(a.size()  + b.size());
        for(int k = 0; k < a.size(); k++)
            System.out.println(a.get(k));
        for(int k = b.size()-1; k > -1; k--)
            System.out.println(b.get(k));
    }
}


class Edge implements Comparable<Edge> {

    int to;
    int from;
    int cost;

    Edge(int a, int b, int c) {
        from = a;
        to = b;
        cost = c;
    }

    @Override
    public int compareTo(Edge t) {
        return t.cost - cost;
    }
}

class Pair implements Comparable<Pair>{

    long x;
    long y;
    
    Pair(long a, long b) {
        x = a;
        y = b;
    }

    @Override
    public boolean equals(Object o) {
        return x == ((Pair)o).x && y == ((Pair)o).y;
    }

    @Override
    public int hashCode() {
        return 1;
    }

    @Override
    public int compareTo(Pair t) {
        if(x >= t.x && y >= t.y)
            return 1;
        return -1;
    }
}

class Reader {

    static BufferedReader reader;
    static StringTokenizer tokenizer;

    public static int pars(String x) {
        int num = 0;
        int i = 0;
        if (x.charAt(0) == '-') {
            i = 1;
        }
        for (; i < x.length(); i++) {
            num = num * 10 + (x.charAt(i) - '0');
        }

        if (x.charAt(0) == '-') {
            return -num;
        }

        return num;
    }

    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input));
        tokenizer = new StringTokenizer("");
    }

    static void init(FileReader input) {
        reader = new BufferedReader(input);
        tokenizer = new StringTokenizer("");
    }

    static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(
                    reader.readLine());
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return pars(next());
    }

    static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }
}