Bài 4 (3 điểm): Hamming

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×5 sẽ là một số trong dãy Hamming, còn 26 = 2×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, . . .

Yêu cầu: Cho số nguyên x (1 ≤ x ≤ 10⁹). Hãy xác định số thứ tự của x trong dãy Hamming.

Dữ liệu vào: Từ tệp văn bản BAI4.INP:

- Dòng đầu tiên chứa số nguyên t – số lượng tests (1 ≤ t ≤ 10⁵),

- Các dòng tiếp theo mỗi dòng chứa một số nguyên x.

Dữ liệu ra: Ghi ra tệp văn bản BAI4.OUT: 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 (-1) nếu không tồn tại số đó trong dãy Hamming.