郭先生的公平游戏

众所皆知，郭先生跟moxin打赌很多次，但是moxin赢的次数太多了，郭先生就觉得不公平,于是郭先生拿出一个方案即扔硬币，但是因为扔一次硬币公平性可能存在问题，于是郭先生决定丢n次，但是丢n次怎么判断胜负呢？

硬币正面朝上为1，反面朝上为0，所以抛n次的结果是一个对应的长度为n的二进制串（正反面出现的概率不一样）

即生成一个二进制串的概率为P(i)，则要求双方获胜的二进制串的集合中，生成对应的二进制串的概率的总和要相等，才能视为方案是公平的

即s₁,s₂,s₃,...s_n为郭先生获胜的二进制串集合S，t₁,t₂,t₃,.....,t_n为moxin获胜的二进制串集合T

∑P(s_i) = ∑P(t_i)    (s_i∈S,t_i∈T) 

为使得方案公平，问去掉的二进制串的数量总和最少是多少？（最少的方案不唯一，你只要保证去掉二进制串的数量总和最小即可）

输入给出一个n(2 <= n <= 1e18) 多组输入

输出去掉的二进制串的数量总和的最小值

3
5
8

4
4
2
[hint]:

    假设n为3（0为反面 1为正面）

    那么010 110 郭先生胜利

    那么001 011 moxin胜利

    000 100 101 111为舍弃的组合 因为没有更少的舍弃方案 所以舍弃的二进制串的数量的总和的最小值为4