U312902 乖乖和咪咪的游戏2

乖乖把宝宝生出来以后又跟咪咪玩了起来～这次他们玩发圈的规则变了。 一开始共有 $N$ 个发圈，乖乖和咪咪轮流拿发圈，乖乖先拿。 每只猫每次最少拿一个，最多拿前一个人拿的个数的两倍（当然拿的个数也不能超过剩下来的发圈数，乖乖第一次拿的个数没有限制）， 拿到最后一个发圈的猫咪赢得这一次游戏。现在乖乖想知道她第一次最少拿多少个发圈的时候她有必胜策略。

一个整数 $N$。

一个整数，表示第一次最少拿多少个发圈的时候她有必胜策略。

对于样例1的解释 4 -> 3 -> 2 -> 0 4 -> 3 -> 1 -> 0 ----- 对于 $20\%$ 的数据，有 $1 \le N \le 10^2$。 对于 $50\%$ 的数据，有 $1 \le N \le 10^3$。 对于 $100\%$ 的数据，有 $1 \le N \le 10^{18}$。