<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

467. Chessmaster
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Ivan Petrovich and Petr Ivanovich enjoy playing chess, especially Ivan Petrovich. Each time he loses regular weekend game in chess, from superfluity of feelings he takes the board and breaks it into separate black and white fields. Well, things were going that way before Petr Ivanovich, frustrated by weekly breakages of his chessboards, replaced usual chessboard by titanic one. Now it was not so easy even to scratch it! But Ivan Petrovich didn't become flustered and, in affective state after usual unsuccessful play, ordered a powerful laser which could burn accurate perfectly round holes through the chessboard.

Only after the laser was delivered Ivan Petrovich realized to his horror that it was not powerful enough: instead of having diameter of a beam equal to the diagonal of a chessboard, his laser had diameter equal to the length of its side! This means that he will be unable to destroy the whole chessboard in one shot, and will have to use the laser several times. But Ivan Petrovich's pension is not large enough to cover bills for electricity after using the laser too frequently, so now he is puzzled with natural question: if he wishes to destroy at least P percents of the chessboard surface, what is the minimum number of laser shots that he have to do?

Help Ivan Petrovich in answering this important and difficult question. And remember: you may shoot only in direction orthogonal to the surface of chessboard, and it is not allowed to move (probably) peeled off parts. Chessboard has the usual form of a perfect square.

Input
Input file contains up to 100 non-negative integer numbers, each on a separate line — percentage of the board P that Ivan Petrovich wants to destroy. Each P will not exceed 100, of course.

Output
For every P in the input file write to the output file on a separate line required minimum number of laser shots. Follow format shown in the example below.

Example(s)
sample input
sample output
1
2
Case #1: 1
Case #2: 1

<|response|>
1. Abridged problem statement
You have a unit‐side square (area = 1). Each laser shot removes a circular hole of radius 0.5 (area = π/4 ≈ 0.7854). Given an integer P (0 ≤ P ≤ 100) denoting the percent of the square's area you want to destroy, compute the minimum number of shots required so that at least P% of the square is removed. Read up to 100 values of P (one per line) until EOF, and for the k-th input Pₖ output
"Case #k: x"
where x is the minimum shots.

2. Key observations
- One shot removes area A₁ = π/4 ≈ 0.7854 ⇒ 78.54% of the square.
  ⇒ If P ≤ 78, one shot suffices.
- Two shots, placed optimally, can cover about 95% of the square ⇒ if 78 < P ≤ 95, need 2 shots.
- Three shots can reach ≈99% coverage ⇒ if 95 < P ≤ 99, need 3 shots.
- To hit exactly 100%, three radius-0.5 circles can't cover the entire square (minimum radius needed is sqrt(65)/16 > 1/2) ⇒ need 4 shots.
- If P = 0, no shots are needed.

3. Full solution approach
Since P is an integer in [0,100] and the coverage thresholds for 1,2,3,4 shots are known from brute-force circle placement and mathematical analysis, we simply compare P against these breakpoints in O(1) per query. Maintain a case counter, read each P until EOF, determine the shot count by a few if-else checks, and print in the required format.

4. C++ implementation with comments
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int p;

void solve() {
    // The trick in this problem is that we can compute the answer in advance and
    // then answer everything in O(1). This should be obvious by realizing that there
    // are only 100 possible values for p, and we can compute the answer for each one.
    //
    // The other observation is that the answer is small, and certainly less than 4. 
    // 1) For cnt = 1, we can cover the whole board with 1 laser. Assuming that the board 
    //    is 1x1, the diameter is sqrt(2) and the radius of the circle is 1/2. Then the
    //    area is pi * (1/2)^2 = pi/4, or roughly 78.5%.
    // 2) For cnt = 2 and cnt = 3, we can simply brute force all positions of the laser,
    //    up to some precision. We can notice that for 3 lasers, it's quite easy to find
    //    a solution with 99% coverage, and for 2 lasers, we can simply use precision that
    //    is roughly 500 and find a solution with 95% coverage.
    // 4) We can show that to get 100% coverage, we need at 3 circles of radius at least
    //    sqrt(65)/16, which is a bit over the radius of 1/2 we have. A relevant page for 
    //    this is: https://www.quora.com/A-unit-square-is-completely-covered-by-three-
    //             identical-circles-Find-the-smallest-possible-diameter-of-the-circles
    //    Hence, the answer of 99% is satisfactory for 3 lasers too, and we don't have to
    //    use too much compute.

    if(p == 0) {
        cout << 0 << '\n';
    } else if(p <= 78) {
        cout << 1 << '\n';
    } else if(p <= 95) {
        cout << 2 << '\n';
    } else if(p <= 99) {
        cout << 3 << '\n';
    } else {
        cout << 4 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    for(int test = 1; cin >> p; test++) {
        cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with comments
```python
import sys

def min_shots(p):
    """
    Given p in [0..100], return the minimum number of radius-0.5 circles
    needed to cover at least p% of the unit square.
    """
    if p == 0:
        return 0
    # One circle covers ~78.54%
    if p <= 78:
        return 1
    # Two circles cover ~95%
    if p <= 95:
        return 2
    # Three circles cover ~99%
    if p <= 99:
        return 3
    # Only four cover 100%
    return 4

def main():
    case_num = 1
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        p = int(line)
        result = min_shots(p)
        print(f"Case #{case_num}: {result}")
        case_num += 1

if __name__ == "__main__":
    main()
```
