Hiện nay, Dịch tả lợn đang hoành hành ở nhiều nước trên thế giới, trong đó có Việt Nam. Tôtô là một bác sỹ thú y nghiên cứu về vi rút phát hiện ra khả năng phân bào rất nhanh của virut cứ mỗi giờ đồng hồ thì từ một con virut sẽ tách các tế bào của nó từ một con thành ba con.

Tôtô muốn có chính các n con virut trong ống nghiệm để nghiên cứu. Bạn hãy giúp Tôtô xem có cách nào đó bỏ ít nhất virut vào ống nghiệm thì sẽ có 1 thời điểm xuất hiện đúng chính xác n virut hay không?

Ví dụ : n = 11 thì đầu tiên bỏ 1 virut sau ba giờ sẽ thành 9 virut và bạn chỉ cần bỏ thêm 2 con nữa là 11 như vậy số virut tốt thiểu là 3

Ví dụ : n = 65 thì đầu tiên bỏ 2 virut sau một giờ sau thành 6 vi rút ta bỏ thêm 1 virut thành 7, hai giờ sau sẽ thành 63 con và bỏ thêm vào đó 2 con sẽ thành 65 như vậy số virut ít nhất là 5.

Input

Dòng đầu tiên là số bộ kiểm thử \(t (1<=t<=100)\)

Dòng tiếp theo có \(t\) số nguyên dương trong đoạn \([1,10^9]\)

Output

Một dòng gồm t số nguyên dương mỗi số cách nhau một khoảng trống là số virut ít nhất từng trường hợp kiểm thử

Input

5
1 6 16 6 2

Output

1 2 4 2 2