moreTimesLess

Some positive integers can be written as the difference of the squares of 2 positive integers, i.e., n = a² - b². For instance, 3 can be written as 2² - 1².

Some numbers can be written in that format in more than one way. For example, 15 can be written as 4² - 1² or 8² - 7².

Your task is, given a positive integer n, to calculate the number of such pairs (a, b), where n = a² - b² and both a and b are positive integers.

Example

• For n = 1, the output should be MoreTimesLess(n) = 0.

  It is impossible to write 1 as a difference of two squares.

• For n = 3, the output should be MoreTimesLess(n) = 1.

  3 = 22 - 12.

• For n = 15, the output should be MoreTimesLess(n) = 2.

  15 = 42 - 12 = 82 - 72.

Input/Output

• [execution time limit] 1.5 seconds

• [input] string n

  Constraints:
  
  1 ≤ n ≤ 107.

• [output] integer

  • The number of pairs (a, b) such that n = a² - b², where a and bare positive integers.