同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21623_StringSequence

2022-5-16 18:19| 发布者: Hocassian| 查看: 19| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-4-89505698678599-Problem List-采集的数据-后羿采集器.html

Pro.ID

21623

Title

String Sequence

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21623

AC

Submit

Ratio

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

Consider a string sequence { S₀, S₁, S₂, ... }, S₀="A". S_i can be constructed by S_i-1: replace every letter "A" in S_i-1 by "AAB", replace every letter "B" by "A". S₀, S₁="AAB", S₂="AABAABA".

Your task is to find the location of the k-th letter "A" in S100. For example, the location of the 1st "A" is 1, the 2nd is 2, the 3th is 4.

输入

Input contains several cases, each case contains an integer k ( 1 ≤ k < 2³¹ ) in one line. Input is terminated by one line contains one zero.

输出

Description

Your task is to find the location of the k-th letter "A" in S100. For example, the location of the 1st "A" is 1, the 2nd is 2, the 3th is 4.

Input

Input contains several cases, each case contains an integer k ( 1 ≤ k < 2³¹ ) in one line. Input is terminated by one line contains one zero.

Output

For each case, output an integer in one line expressing the location of the k-th "A".

Sample Input

1
2
3
4
5
0

Sample Output

1
2
4
5
7

Source

11th ZD 2008

样例输入