ZERO - Biến đổi về số 0
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.5 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

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 𝑁 (𝑁 ≤ 106);

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.

Ví dụ

Input

2
3
3

Output

3
3


Nguồn: 3D 20162017

Back to Top