時間制限 : sec, メモリ制限 : KB
Japanese

短歌数

願はくは 花の下にて 春死なむ そのきさらぎの 望月のころ

これは,西行法師が詠んだとされる,有名な短歌の一つである. 短歌は,日本において古くから親しまれている和歌の一種であり,その多くは 5・7・5・7・7 の五句三十一音からなる.

ところで,57577 という数は,5 と 7 の二種類の数字からなる. このような,十進表記がちょうど二種類の数字からなる正の整数を,短歌数と呼ぶことにする. 例えば,10, 12, 57577, 25252 などは短歌数であるが,5, 11, 123, 20180701 などは短歌数ではない.

正の整数 N が与えられる.N 番目に小さい短歌数を求めよ.

Input

入力は最大で 100 個のデータセットからなる.各データセットは次の形式で表される.

N

整数 N1 ≤ N ≤ 1018 を満たす.

入力の終わりは 1 つのゼロからなる行で表される.

Output

各データセットについて,N 番目に小さい短歌数を 1 行に出力せよ.

Sample Input

1
2
3
390
1124
1546
314159265358979323
0

Output for the Sample Input

10
12
13
2020
25252
57577
7744444777744474777777774774744777747477444774744744