Bạn được cho số nguyên dương n. Trong một phép tính, bạn có thể là nhân n với 2, hoặc là chia n cho 6 (nếu n chia hết cho 6). Bạn hãy tìm số lượng phép tính ít nhất cần thực hiện để có thể đưa số nguyên n này về số 1 hoặc trả lời rằng không thể đưa số nguyên n về 1 được.

Dòng đầu tiên gồm một số nguyên duy nhất là số nguyên dương t, (1 \leq t \leq 10^5) - số test mà bạn cần phải trả lời. Tiếp theo là t bộ dữ liệu.

Với mỗi bộ dữ liệu, dòng đầu tiên gồm duy nhất một số nguyên dương n, (1 \leq n \leq10^9).

Với mỗi test, bạn hãy in ra câu trả lời là số lượng phép tính ít nhất cần thực hiện để đưa n về 1. Nếu không có cách nào đưa n vào 1, hãy in ra -1.