短歌数

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

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

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

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

Input

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

N

æ•´æ•° N は 1 ≤ N ≤ 10¹⁸ を満たす．

入力の終わりは 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