409_F. 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
```python
print([0,1,1,1,2,1,2,1,5,2,2,1,5,1,2,1,14,1,5,1,5,2,2,1,15,2,2,5,4,1,4,1,51,1,2,1,14,1,2,2,14,1,6,1,4,2,2,1,52,2,5,1,5,1,15,2,13,2,2,1,13,1,2,4,267,1,4,1,5,1,4,1,50,1,2,3,4,1,6,1,52,15,2,1,15,1][int(input())])

```