Bạn được cho \(q\) truy vấn, mỗi truy vấn được cho một số nguyên \(N\). Bạn có thể thực hiện bất kỳ 1 trong 2 thao tác sau:

1: Nếu có thể tách \(N\) thành hai số \(a\) và \(b\) sao cho \(N = a \times b\ (a ≠ \ 1,\ b ≠ 1)\) thì có thể chuyển \(N = max(a,b)\)

2: Giảm giá trị của \(N\) xuống 1

Hãy cho biết số thao tác ít nhất để chuyển số \(N\) thành 0.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(q\) là số lượng truy vấn.

+ \(q\) dòng tiếp theo, mỗi dòng ghi một số nguyên \(N\)

Giới hạn:

\[1 \leq q \leq 10^{3}\]

\[0 \leq N \leq 10^{6}\]

Ví dụ:

Input	Output
2 3 4	3 3

Giải thích:

\(3 \rightarrow 2 \rightarrow 1 \rightarrow 0\): 3 bước

\(4 \rightarrow 2 \rightarrow 1 \rightarrow 0\): 3 bước