Factstone Benchmark

Time limit1sMemory limit128 MB

Summary

For each year, compute the word size by doubling every decade from 4 bits in 1960, then find the largest n with n! <= 2^b - 1.

Level: Medium5 of 10
Topics: Math, Binary search, Prefix sum, Implementation
Solved: No attempts yet

Problem

Amtel has announced that it will release a 128-bit computer chip by 2010, a 256-bit computer by 2020, and so on, continuing its strategy of doubling the word size every ten years. (Amtel released a 64-bit computer in 2000, a 32-bit computer in 1990, a 16-bit computer in 1980, an 8-bit computer in 1970, and its very first computer, a 4-bit machine, in 1960.)

Amtel will use a new benchmark, the Factstone, to advertise the vastly improved capacity of its new chips. The Factstone rating is defined as the largest integer $n$ such that $n!$ can be stored as an unsigned integer in a single computer word. In other words, if the word size is $b$ bits, then a word can hold any value from $0$ to $2^b - 1$ , so the Factstone rating is the largest integer $n$ with $n! \le 2^b - 1$ .

Given a year $y$ ( $1960 \le y \le 2160$ ), what is the Factstone rating of Amtel's most recently released chip at that time?

Input

The input consists of several test cases. Each test case is a single line containing the year $y$ . A line containing $0$ follows the last test case and marks the end of input.

Output

For each test case, output the Factstone rating on its own line.

Examples1

Example 1
Input
```
1960
1981
0
```
Expected output
```
3
8
```