Edogawa Conan là một thám tử nhí tài ba với bộ óc suy luận sắc bén cùng niềm đam mê giải mã những vụ án hóc búa. Một ngày nọ, văn phòng thám tử Mori nhận được một bức thư thách đấu kỳ lạ từ siêu đạo chích Kaito Kid nhằm báo trước về phi vụ đánh cắp viên đá quý Pandora. Thay vì ghi rõ thời gian và địa điểm, Kid chỉ để lại một danh sách gồm những con số khổng lồ kèm theo lời gợi ý về "Chuỗi số vàng của tự nhiên". Bị cuốn hút bởi thử thách trí tuệ này, Conan lập tức bắt tay vào phân tích và nhận ra rằng chìa khóa của mật mã nằm ở dãy số Fibonacci huyền thoại.

Không phải là những con số ngẫu nhiên, mật mã của Kaito Kid được xây dựng dựa trên một cấu trúc toán học vô cùng chặt chẽ và logic:

• Cấu trúc dãy mật mã:

  • Dãy số Fibonacci được xác định bắt đầu từ chỉ số ~1~ với quy luật kinh điển: ~F_1 = 1, F_2 = 1~, và với mọi ~i \geq 3~ thì ~F_i = F_{i-1} + F_{i-2}~.

• Quy tắc giải mã hệ thống: Trong bức thư, Kaito Kid đưa ra ~Q~ câu đố, mỗi câu đố là một số nguyên dương ~M~:

  • Để mở được từng lớp khóa bảo vệ viên đá quý ứng với số ~M~, Conan cần xét số Fibonacci thứ ~M~.
  • Mật khẩu của lớp khóa chính là số lượng các giá trị Fibonacci phân biệt là ước của ~F_M~.

Thời gian trước giờ hành động của Kaito Kid đang cạn dần trong khi các chỉ số ~M~ lại vô cùng lớn, vượt xa khả năng tính toán thủ công của Tiến sĩ Agasa. Bạn hãy lập trình giúp thám tử Conan giải mã thật nhanh toàn bộ ~Q~ câu đố này nhé!

Input

• Dòng đầu tiên chứa một số nguyên dương ~Q~ là số lượng câu đố trong bức thư ~(Q \leq 10^6)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~M~ thể hiện chỉ số của số Fibonacci cần giải mã ~(M \leq 10^{18})~.

Output

• Gồm ~Q~ dòng, mỗi dòng in ra một số nguyên duy nhất là số lượng giá trị Fibonacci phân biệt là ước của ~F_M~ tương ứng.

Example Input

2
5
6

Example Output

2
3

Giải thích

• Các số đầu tiên trong dãy Fibonacci là: ~F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5, F_6 = 8~.
• Với ~M = 5~: Ta có ~F_5 = 5~. Các giá trị thuộc dãy Fibonacci đồng thời là ước của ~5~ gồm: ~1~ và ~5~. Có tất cả ~2~ giá trị phân biệt.
• Với ~M = 6~: Ta có ~F_6 = 8~. Các giá trị thuộc dãy Fibonacci đồng thời là ước của ~8~ gồm: ~1, 2~ và ~8~ (số ~4~ là ước của ~8~ nhưng không thuộc dãy Fibonacci). Có tất cả ~3~ giá trị phân biệt.

Ràng buộc

• Subtask ~1~ (~15\%~ số điểm): ~Q \leq 100~ và ~M \leq 90~.
• Subtask ~2~ (~15\%~ số điểm): ~Q \leq 100~ và ~M \leq 500~.
• Subtask ~3~ (~15\%~ số điểm): ~M \leq 500~.
• Subtask ~4~ (~15\%~ số điểm): ~Q \leq 100~ và ~M \leq 10^5~.
• Subtask ~5~ (~15\%~ số điểm): ~Q \leq 100~ và ~M \leq 10^{12}~.
• Subtask ~6~ (~5\%~ số điểm): ~M \leq 10^7~.
• Subtask ~7~ (~5\%~ số điểm): ~Q \leq 100~ và ~M \leq 10^{14}~.
• Subtask ~8~ (~5\%~ số điểm): ~Q \leq 100~.
• Subtask ~9~ (~5\%~ số điểm): ~Q \leq 1000~.
• Subtask ~10~ (~5\%~ số điểm): ~Q \leq 10^4~.