Bạn được cho ~ q ~ câu hỏi, mỗi câu hỏi được cho một số nguyên dương ~ n ~. Hãy cho biết số bước ít nhất cần thực hiện thao tác để số ~ n ~ trở thành số 0. Biết rằng ở mỗi bước bạn có thể thực hiện 1 trong hai thao tác sau: 1. Nếu ~ a × b = n ~ ~ ( a ≠ 1 , b ≠ 1 ) ~ thì có thể đổi ~ n ~ thành ~ max⁡(a,b) ~ 2. Giảm giá trị của ~ n ~ đi 1

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên ~ q ~ ~ (1 ≤ q ≤ 10^3 ) ~
• ~ q ~ dòng tiếp theo, mỗi dòng ghi một số nguyên dương ~ n ~ ~ (1 ≤ n ≤ 10^6) ~

Kết quả

Gồm ~ q ~ dòng, mỗi dòng ghi một số nguyên cho biết số bước ít nhất cần thực hiện tương ứng với truy vấn trong input

Ràng buộc

Ví dụ:

Input 1

```2 3 4

```

Output 1

3
3