Problem E. Square coins ≡

• problems
• en ru
 Author: Anton Karabanov Time limit: 1 sec Input file: Standard input Memory limit: 512 Mb Output file: Standard output

Statement

"Sensational discovery!", "Archaeologists have found an ancient civilization!", "Scientists are amazed at the development of ancient technologies!" — news were full of such headlines. The artifacts discovered under the thick sand of the Sahara Desert were indeed amazing: perfect instruments and mechanisms, manuscripts and parchments with incomprehensible records, objects of art and everyday life - everything pointed to a highly developed civilization that once existed in this region. Scientists prepared for long and painstaking work.

Numismatists, of course, were interested in the monetary system of the Ancient Saharians (this is how the discovered civilization was dubbed). Gold coins of various sizes were found, all exclusively square in shape and with a square hole in the middle. Interestingly, all sizes (both sides of coins and sides of holes) were odd numbers. It was suggested that the value of the coin corresponded to its area: for example, 24 points were minted on a coin of size 5 with hole 1, 16 points were found on a coin of size 5 with hole 3, and 8 points are clearly visible on a coin of size 3 with hole 1. Everything indicated that the value of the coin was equal to the difference between the squares of the side of the coin and the side of the hole: 52 − 12 = 24, 52 − 32 = 16, 32 − 12 = 8.

Given the value of the coin, determine all of its possible sizes.

Input format

Input contains an integer n — coin value. It is guaranteed that n is divisible by eight.

Output format

On the first line output integer k — number of different possible coin sizes. On each of the the next k lines output two numbers: size of the coin and the size of the hole. Order lines by ascending coin size.

8 ≤ n ≤ 1012

Notes on sample

In the sample the coin value 72 is given. There are three corresponding sizes: 92 − 32 = 81 − 9 = 72, 112 − 72 = 121 − 49 = 72 и 192 − 172 = 361 − 289 = 72.

Sample tests

No. Standard input Standard output
1
72
3
9 3
11 7
19 17

0.108s 0.018s 17