000001

Input

The input contains a single integer a (1 ≤ a ≤ 64).

Output

Output a single integer.

Examples

Input

2

Output

1

Input

4

Output

2

Input

27

Output

5

Input

42

Output

6

inputFormat

Input

The input contains a single integer a (1 ≤ a ≤ 64).

outputFormat

Output

Output a single integer.

Examples

Input

2

Output

1

Input

4

Output

2

Input

27

Output

5

Input

42

Output

6

样例

27

5