Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Spongebob and Squares

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSpongebob 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* ≤ 10^{18}) — 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.

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 00:30:50 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|