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();
        ArrayList<String> a = new ArrayList();
        ArrayList<String> b = new ArrayList();
        
        i = 1; j = n;
        
        while(i < 2000000){
            long x = bin(i, j, n);
            
            if(x == -1){
                i++;
                continue;
            }
            
            a.add(i + " " + j);
            if(i != j)
              b.add(j + " " + i);
            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));
    }
    
    static long bin(long first, long last, long n){
        long i = first;
        while(first <= last){
            long mid = (first + last) / 2;
            long x = calc(i, mid);
            
            if(x > n)
                last = mid-1;
            else if(x < n)
                first = mid + 1;
            else{
                j = mid;
                return mid;
            }
        }
        j = last;
        return -1;
    }
  
   
    static long calc(long n, long m){
        return (3*m*n*n + 3*m*n - (n*n*n) + n)/6;
        
    }
}


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());
    }
}