Because of necessary software maintenance, Jutge.org may not work well on the afternoons of the 20th and 21th of april.

Odd Catalan numbers P75985

Statement

html

The famous Catalan numbers can be defined by the recurrence

C_n =

n−1

∑

i=0

C_i · C_n−i−1 ,

with C₀ = 1. The first Catalan numbers are 1, 1, 2, 5, 14, 42, 132, …

You are given an index i. What is the smallest j such that j ≥ i and C_j is odd?

Input

Input consists of several cases, each with a natural number no larger than 10¹⁵.

Output

For every i, print the smallest j such that j ≥ i and C_j is odd. If such a number does not exist, print “Catalans are strange!”.

Public test cases

Input

0
1
2
3
1099511627768

Output

0
1
3
3
1099511627775

Information