Consider Pascal’s triangle modulo 2. The first nine rows are given below:

        1 
       1 1 
      1 0 1 
     1 1 1 1 
    1 0 0 0 1 
   1 1 0 0 1 1 
  1 0 1 0 1 0 1 
 1 1 1 1 1 1 1 1 
1 0 0 0 0 0 0 0 1 

Let F(n) be the number of 1 in the first n rows. So that F(0) = 0, F(1) = 1, F(2) = 3, etc.

Given a, find the smallest integer n such that F(n) ≥ a. Let N(a) denote this integer.

Input

A list of integers a₁, ..., a_l, between 0 and 10¹⁸, one per line.

Output

The integers N(a₁), ..., N(a_l), one per line.

Example

input:
0
1
4
15

output:
0
1
3
6