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 PYTHON3):

Solution:
from functools import reduce
from itertools import islice, product
from operator import mul


def prod(iterable, start=1):
    return reduce(mul, iterable, start)


def isqrt(n):
    x, px, nx = 0, 0, n
    while nx not in (x, px):
        px, x = x, nx
        nx = (x + (n//x))//2
    return min(x, nx)


def relevant_factors(n):
    # print("n={}".format(n))
    for i in range(2, 2000000):
        if i**2 > n:
            break
        c = 0
        q, r = divmod(n, i)
        while not r:
            c += 1
            n = q
            q, r = divmod(n, i)
        if c:
            # print("i={}, c={}, n={}".format(i, c, n))
            yield (i, c)

    if n > 1:
        sn = isqrt(n)
        # print("sn={}".format(sn))
        if sn * sn == n:
            yield (sn, 2)
        elif sn * (sn+1) == n:
            yield (sn, 1), (sn+1, 1)
        else:
            yield (n, 1)


def divisors(fp):
    return sorted(prod(t) for t in product(*[powers(f, e+1) for f, e in fp]))


def powers(b, e):
    k = 1
    for _ in range(e):
        yield k
        k *= b


def tables(n):
    if (n == 1):
        return [(1, 1)]

    t = set()
    n6 = 6*n
    for a in divisors(relevant_factors(n6)):
        q, r = divmod(n6, a*(a+1))
        if r:
            continue
        b, r = divmod(q + a - 1, 3)
        if r:
            continue
        if b < a:
            continue
        t.add((a, b))
        t.add((b, a))
    return sorted(t)


if __name__ == '__main__':
    n = int(input())
    ts = tables(n)
    print(len(ts))
    for t in ts:
        print("{} {}".format(*t))