Cho một số nguyên dương ~n~, mỗi bước bạn có thể thực hiện một trong ba phép biến đổi sau:

• Trừ ~n~ đi 1
• Chia ~n~ cho 2 nếu ~n~ chia hết cho 2
• Chia ~n~ cho 3 nếu ~n~ chia hết cho 3

Yêu cầu:Tìm số bước biến đổi ít nhất để ~n~ có giá trị là 1.

Input

• Dòng đầu ghi số ~t~ cho biết số lượng bộ test (~t \le 100~).
• ~t~ dòng tiếp theo, mỗi dòng ghi một số nguyên dương ~n~.

Giới hạn:

• 40% số test có ~n~ <= 20.
• 60% số test còn lại có ~n~ <= 10^5.

Output

Gồm ~t~ dòng, mỗi dòng ghi một số nguyên cho biết kết quả tương ứng.

Sample

Input #1

2
7
10

Output #1

3
3