The famous Catalan numbers can be defined by the recurrence
C_{n} = |
| C_{i} · C_{n−i−1} , |
with C_{0} = 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^{15}.
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!”.
Input
0 1 2 3 1099511627768
Output
0 1 3 3 1099511627775