Minimum Fourth Power Sum Decomposition

Given an integer ( m ), decompose it as the sum of fourth powers, i.e., find the minimum number ( n ) such that ( m = a_1^4 + a_2^4 + \cdots + a_n^4 ).

For example, when ( m = 706 ), we have ( 706 = 5^4 + 3^4 ), so ( n = 2 ). It can be proved that this ( n ) is minimal.

inputFormat

The input consists of a single integer ( m ).

outputFormat

Output the minimum number ( n ) such that ( m ) can be expressed as the sum of ( n ) fourth powers.

sample

706

2