Problem: As usual, those who called wolves get together on 8 p.m. at the supermarket. The thing they want is only one, a box lunch that is labeled half price. Scrambling for a few discounted box lunch, they fiercely fight every day. And those who are blessed by hunger and appetite the best can acquire the box lunch, while others have to have cup ramen or something with tear in their eyes.

A senior high school student, Sato, is one of wolves. A dormitry he lives doesn't serve a dinner, and his parents don't send so much money. Therefore he absolutely acquire the half-priced box lunch and save his money. Otherwise he have to give up comic books and video games, or begin part-time job.

Since Sato is an excellent wolf, he can acquire the discounted box lunch in 100% probability on the first day. But on the next day, many other wolves cooperate to block him and the probability to get a box lunch will be 50%. Even though he can get, the probability to get will be 25% on the next day of the day. Likewise, if he gets a box lunch on a certain day, the probability to get on the next day will be half. Once he failed to get a box lunch, probability to get would be back to 100%.

He continue to go to supermaket and try to get the discounted box lunch for n days. Please write a program to computes the expected value of the number of the discounted box lunches he can acquire.

Constraints

* 1 ≤ n ≤ 100,000

Input

Input consists of several datasets.

Input for a single dataset is given as a single integer n.

Input terminates with a dataset where n = 0.

Output

For each dataset, write a line that contains an expected value. You may print any number of digits after the decimal point. Answers that have an error less than 1.0e-2 will be accepted.

Example

Input

1
2
3
0


Output

1.00000000
1.50000000
2.12500000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

double P[100010]; // iテ・ツ崢榲ゥツ?」テァツカツ堙」ツ?ァテ・ツ仰敕」ツ?、テァツ「ツコテァツ篠?
double dp[100010]; // iテヲツ猟・テァツ崢ョテ」ツ?セテ」ツ?ァテ」ツ?ォテ・ツセツ療」ツつ嘉」ツつ古」ツつ凝ァツ堋ソテ」ツ?ョテヲツ慊淌・ツセツ?・ツ?、

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  P[1] = 1.0;
  double p = 0.5;
  reps(i, 2, 100010) {
    P[i] = P[i-1] * p;
    p /= 2.0;
  }
  dp[1] = 1.0;
  reps(i, 2, 100010) {
    double p = 0.5;
    reps(j, 1, min(i, 100LL)) {
      // j+1テヲツ猟・テァツ崢ョテ」ツ?ァテ・ツ按敕」ツつ?」ツ?ヲティツイツ?」ツ?妥」ツつ凝」ツ?ョテ」ツ?ッテ」ツ?‾[j]*(1-p)テ」ツ?ョテァツ「ツコテァツ篠?」ツ?ァティツオツキテ」ツ?禿」ツつ?
      // テ」ツ?敕」ツつ古」ツ?セテ」ツ?ァテ」ツ?ォjテヲツ楪堙」ツ?ョテァツ堋ソテ」ツつ津・ツセツ療」ツ??」ツ?敕」ツつ古」ツ?ォテ・ツ環?」ツ?暗」ツ?ヲテヲツョツ凝」ツつ格-j-1テヲツ猟・テゥツ鳴禿」ツ?ョテァツ堋ソテ」ツ?ョテヲツ慊淌・ツセツ?・ツ?、テ」ツつ津・ツセツ療」ツつ?
      // テヲツョツ凝」ツつ格-j-1テヲツ猟・テゥツ鳴禿」ツ?ョテァツ堋ソテ」ツ?ョテァツ堋ソテ」ツ?ョテヲツ慊淌・ツセツ?・ツ?、テ」ツ?ッテ」ツ??テヲツ猟・テァツ崢ョテ」ツ?凝」ツつ永-j-1テァツ崢ョテ」ツ?セテ」ツ?ァテ」ツ?ョテヲツ慊淌・ツセツ?・ツ?、テ」ツ?ォテァツュツ嘉」ツ?療」ツ??
      dp[i] += P[j]*(1-p)*(j+dp[i-j-1]);
      p /= 2.0;
    }
    // P[i]テ」ツ?ョテァツ「ツコテァツ篠?」ツ?ァテ・ツ仰敕」ツ?。テァツカツ堙」ツ?妥」ツつ凝」ツ?ィiテヲツ楪堙」ツつ津・ツセツ療」ツつ?
    dp[i] += i*P[i];
  }

  int n;
  while(cin >> n, n) {
    cout << dp[n] << endl;
  }

  return 0;
}