Cho số nguyên \(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 \(a\) và \(b\) mà \(N = a \cdot b\) (\(a \neq 1, b \neq 1\)) thì bạn có thể biến đổi \(N = \max(a, b)\);
2. Giảm giá trị của \(N\) 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ố \(N\) thành số \(0\).

Input

• Dòng đầu tiên chứa số nguyên dương \(Q\) (\(1 \le Q \le 1000\)) là số lượng bộ dữ liệu;
• \(Q\) dòng tiếp theo, dòng thứ \(i\) mô tả bộ dữ liệu thứ \(i\): chứa duy nhất một số nguyên \(N\) (\(0 \le N \le 10^6\)).

Output

• Ghi ra \(Q\) dòng, dòng thứ \(i\) ghi câu trả lời cho bộ dữ liệu thứ \(i\) tương ứng.

Example

2
3
3

3
3

Constraints

• \(1 \le Q \le 1000\)
• \(0 \le N \le 10^6\)