### Problem

Robodevil likes to do some mathematics between rehearsals of his orchestra. Today he invented devilish sequence No. 1729:

• x0 = 0,
• x1 = 1,
• xn = (xn − 1 + xn − 2) / 2.

For example, x10 = 0.666015625. Robodevil became interested at once how many sixes there were at the beginning of an arbitrary xn. In 6 nanoseconds, he had a formula. Can you do the same?

### Code

```import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

final static int scalc = 102400;

void solve() {
Scanner cin = new Scanner(System.in);
int N = cin.nextInt();
BigInteger t = new BigInteger("6").shiftLeft(N-2);
BigDecimal var = new BigDecimal("2");
var = var.divide(BigDecimal.valueOf(3), scalc, BigDecimal.ROUND_DOWN);
BigDecimal sub = BigDecimal.ONE.divide(new BigDecimal(t), scalc, BigDecimal.ROUND_DOWN);
BigDecimal ans;
if((N % 2) == 0) ans = var.subtract(sub);
String res = ans.toString();
int cnt = 0;
for(int i = 2; i < res.length(); ++i) {
if(res.charAt(i) == '6') ++cnt;
else break;
}
System.out.println(cnt);
}

public static void main(String[] args) {
new Main().solve();
}
}
```