Description

根据小屈的苦学，发现任何一个正整数可以唯一地表示成​不连续的斐波那契数的和（Zeckendorf 表示），例如：

10=8+2(对应斐波那契数列 1,2,3,5,8,…，不用相邻） 20=13+5+2 这里斐波那契从F1=1,F2=2,F3​=3,F4=5,… 开始（即不含两个 1）。

定义 G(x) 为 x 的 Zeckendorf 表示中​所用到的斐波那契数的下标之和​。 10 = F5 + F2因为 F5=8, F2=2，所以 G(10) = 5 + 2 = 7。

20 = F6 + F4 + F2（因为 F6=13, F4=5, F2=2），所以 (G(20) = 6 + 4 + 2 = 12)。

Format

Input

一个整数N

Output

如果G(N)是奇数输出1,不是输出0

Samples

10

1

Limitation

1s, 1024KiB for each test case.