Matryoshka là một loại búp bê xuất xứ từ Nga hơn một thế kỷ trước. Đặc trưng của chúng là một bộ búp bê có kích thước khác nhau, trong đó búp bê nhỏ nằm vừa vặn bên trong búp bê lớn.

Trong bài này, ta làm việc với matrygon: các bộ đa giác lồi đều có kiểu lồng nhau tương tự. Một matrygon gồm các đa giác lồi đều có diện tích dương \(p_1,p_2,\ldots,p_k\) sao cho với mọi \(i\), các đỉnh của \(p_{i+1}\) trùng với một tập con thực sự các đỉnh của \(p_i\); tức \(p_{i+1}\) có ít đỉnh hơn hẳn \(p_i\).

Hai hình sau minh họa hai matrygon. Hình thứ nhất có ba đa giác lồi đều: một đa giác \(24\) cạnh, một lục giác đều \(6\) cạnh và một tam giác đều \(3\) cạnh. Hình thứ hai có hai đa giác: một đa giác đều \(22\) cạnh và một đa giác đều \(11\) cạnh. Tổng số cạnh của các đa giác trong mỗi matrygon đều bằng \(33\).

Cho tổng số cạnh cố định \(N\), hãy tính số đa giác lớn nhất có thể thuộc một matrygon sao cho tổng số cạnh của mọi đa giác đúng bằng \(N\).

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi dòng tiếp theo chứa một số nguyên \(N\), là tổng số cạnh mục tiêu của một bộ dữ liệu.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ \(1\)), còn \(y\) là số đa giác lớn nhất trong một matrygon có tổng số cạnh đúng bằng \(N\).

Ràng buộc

• \(1\le T\le100\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(3\le N\le1000\).
• Test Set 2 (Visible Verdict): \(3\le N\le10^6\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
33
15
41

Case #1: 3
Case #2: 2
Case #3: 1

Nguồn

Google Code Jam 2021, Vòng 2, bài Matrygons.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.