Cho số nguyên dương N (N<231). Chỉ được phép sử dụng hai thao tác A, B dưới đây, hãy dịch chuyển N về 1 sao cho số các thao tác A, B được thực hiện ít nhất.

            Thao tác A: Biến đổi N = N-1.

            Thao tác B: Biến đổi N = max(u, v), trong đó u*v = N (u>1, v>1).

Ví dụ N = 17 được thực hiện ít nhất 4 bước A, B như sau:

            Thao tác A: N = N – 1 = 17-1 = 16

            Thao tác B: N = max (u, v) = max(4*4) = 4

            Thao tác B: N = max (u, v) = max(2*2) = 2

            Thao tác A: N = N-1 = 2-1 = 1 

Input

• Dòng đầu tiên ghi lại T là số lượng bộ test (T≤50).
• Mỗi bộ test gồm một dòng ghi lại một số nguyên không âm.

Output

• Ứng với mỗi bộ test đưa ra số các bước A, B thực hiện ít nhất để dịch chuyển test tương ứng về 1