Count how many staircases of a given total size can be built using step sizes that divide the total evenly.
Problem
Petya wants to build a staircase with a total of cubes. A staircase is formed by several steps, where each step has a positive integer height, and the step heights are strictly increasing from left to right.
A valid staircase must use exactly cubes in total. Among all possible staircases, Petya is interested in those where the greatest common divisor of all step heights is greater than 1, so that every step height is divisible by the same integer larger than 1.
Your task is to determine the largest possible number of steps in such a staircase. If no such staircase exists, output 0.
Notes
- Step heights must be positive integers.
- The staircase must use all cubes exactly once.
- Heights are strictly increasing, so a sequence like $1,2,3 is valid, but \1,1,2$ is not.
Input Format
- The first line contains one integer .
- is the total number of cubes.
Output Format
- Print one integer: the maximum number of steps in a valid staircase, or 0 if it is impossible.
Constraints
- is an integer.
- The exact official bounds are not provided in the source metadata, but the intended solution is based on checking divisors of .
Example 1
Input
6
Output
2
Explanation
One valid staircase is heights 2 and 4, which are strictly increasing and sum to 6. No staircase with more than 2 steps satisfies the condition.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.