Cho số nguyên 𝑁, tại mỗi bước, bạn được thực hiện một trong hai phép biến đổi sau:

1. Nếu có hai số nguyên dương 𝑎 và 𝑏 mà 𝑁 = 𝑎 × 𝑏 (𝑎 ≠ 1, 𝑏 ≠ 1) thì bạn có thể biến đổi 𝑁 = max(𝑎, 𝑏);
2. Giảm giá trị của 𝑁 xuống 1 đơn vị.

Yêu cầu: Hãy tính số phép biến đổi ít nhất để biến đổi số 𝑁 thành số 0.

Dữ liệu:

- Dòng đầu tiên chứa số nguyên dương 𝑄 (1 ≤ 𝑄 ≤ 1000) là số lượng bộ dữ liệu;
- 𝑄 dòng tiếp theo, dòng thứ 𝑖 mô tả bộ dữ liệu thứ 𝑖: chứa duy nhất môt ṣ ố nguyên 𝑁 (𝑁 ≤ 10⁶);

Kết quả:

Ghi ra 𝑄 dòng, dòng thứ 𝑖 ghi câu trả lời cho một bộ dữ liệu thứ 𝑖 tương ứng trong file dữ liệu vào.