Vida nói rằng cô ấy mang dòng máu Elf: ít nhất một trong những tổ tiên của cô ấy là Elf. Nhưng cô ấy không biết đó là cha mẹ (1 thế hệ trước), ông bà (2 thế hệ trước), hay một người nào đó từ nhiều thế hệ trước nữa. Hãy giúp cô ấy!

Quy tắc di truyền dòng máu Elf hoạt động như sau: Nếu một người cha/mẹ là Elf tỉ lệ A/B, và người còn lại là Elf tỉ lệ C/D, thì con của họ sẽ là Elf tỉ lệ (A/B + C/D) / 2. Ví dụ, nếu một người là Elf 0/1 (người thuần chủng) và một người là Elf 1/2 có con, đứa trẻ đó sẽ là Elf 1/4.

Vida chắc chắn về một điều: 40 thế hệ trước, cô ấy có \(2^{40}\) tổ tiên khác nhau, và mỗi người trong số họ hoặc là Elf 1/1 hoặc là Elf 0/1.

Vida nói cô ấy là Elf tỉ lệ P/Q. Hãy cho cô ấy biết số thế hệ tối thiểu trước đây có thể có một người là Elf 1/1 trong gia đình cô ấy. Nếu Vida không thể là Elf tỉ lệ P/Q, hãy thông báo rằng cô ấy đã nhầm!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, T. T dòng tiếp theo, mỗi dòng chứa một phân số có dạng P/Q, trong đó P và Q là các số nguyên.

Dữ liệu ra

Với mỗi bộ test, xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số thế hệ tối thiểu trước đây có thể có một Elf 1/1 nếu cô ấy là Elf tỉ lệ P/Q. Nếu không thể, y phải là chuỗi "impossible".

Ràng buộc

• \(1 \le \mathbf{T} \le 100\).

Phân nhóm

• Small dataset:

  • \(1 \le \mathbf{P} < \mathbf{Q} \le 1000\).
  • P và Q không có ước chung (phân số tối giản).

  • Large dataset:

  • \(1 \le \mathbf{P} < \mathbf{Q} \le 10^{12}\).

  • P và Q có thể có ước chung (phân số không nhất thiết tối giản).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
1/2
3/4
1/4
2/23
123/31488

Case #1: 1
Case #2: 1
Case #3: 2
Case #4: impossible
Case #5: 8

Nguồn

Google Code Jam 2014, Vòng 1C, bài Part Elf.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.