Dãy số nguyên dương tăng dần, trong đó ước nguyên tố của mỗi số không quá 5 được gọi là dãy Hamming. Như vậy, ~10 = 2 \times 5~ sẽ là một số trong dãy Hamming, còn ~26 = 2 \times 13~ không thuộc dãy Hamming.

Phần đầu của dãy Hamming là ~1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, \dots~

Yêu cầu: Cho số nguyên ~x~ (~1 \le x \le 10^{18}~). Hãy xác định số thứ tự của ~x~ trong dãy Hamming.

Input

• Dòng đầu tiên chứa số nguyên ~t~ – số lượng tests (~1 \le t \le 10^5~).
• Mỗi dòng tiếp theo chứa một số nguyên ~x~.

Output

• Kết quả mỗi test đưa ra trên một dòng dưới dạng số nguyên hoặc thông báo ~Not in sequence~.

Sample Input 1

4
1
2
6
14

Sample Output 1

1
2
6
Not in sequence