Dr. Patel đang thực hiện bài phỏng vấn cho công ty Gooogle. Bài phỏng vấn của Dr. Patel như sau:

Cho một xâu ký tự ~S~ có độ dài ~N~. Yêu cầu tìm xâu con liên tiếp có kí tự giống nhau dài nhất trong xâu ký tự ~S~.

Input

• Dòng đầu tiên chứa 1 số ~T~ là số bộ test ~(1 \leq T \leq 100)~.
• Với mỗi bộ test, gồm 2 dòng, dòng đầu tiên là số nguyên ~N~ ~(1 \leq N \leq 10^5)~ và một xâu ký tự ~S~ chỉ gồm các ký tự in hoa.

Output

• Gồm ~T~ dòng là kết quả cho từng test. Giống như định dạng của sample.

Sample

Input #1

3
9
BBCCZZZZO
17
GGOOOOOOOOOGLEEEE
1
G

Output #1

Case #1: 4
Case #2: 9
Case #3: 1

Giải thích #1

Chẳng hạn BBCCZZZZO có Z gồm 4 ký tự gần nhau nhiều nhất nên in ra ~4~, tương tự với GGOOOOOOOOOGLEEEE có 9 chữ O gần nhau nhiều nhất nên in ra ~9~.

Dr. Patel đang chơi trò chơi với con gái của mình nhân ngày sinh nhật của cô bé. Trò chơi được diễn ra như sau:

Bắt đầu từ Dr. Patel đi trước, ông chọn 1 số ~N~ và kiểm tra xem nếu nó tồn tại một số ~X~ mà ~2^X = N~, họ chia ~N~ cho ~2~. Nếu không họ giảm ~N~ đi bằng phép toán ~N - 2^Y~ sao cho ~2^Y < N~ và ~2^Y~ là lớn nhất. Cho tới khi ai thực hiện 1 trong 2 phép toán trên ra ~1~, người đó giành chiến thắng.

Yêu cầu: Cho một số ~N~ hãy giúp Dr. Patel tính xem liệu ông ấy có thể giành chiến thắng hay không?

Input

• Dòng đầu gồm 1 số nguyên ~T~ là số bộ test ~(1 \leq T \leq 10^5)~.
• ~T~ dòng tiếp theo, mỗi dòng gồm 1 số nguyên dương ~N~ ~(1 \leq N \leq 2^{64} - 1)~.

Output

• Gồm ~T~ dòng ứng với mỗi test, nếu Dr. Patel có thể chiến thắng in ra yes ngược lại in ra no.

Sample

Input #1

2
132
6

Output #1

Case #1: yes
Case #2: no

Dr. Patel đang bảo vệ luận án tiến sĩ của mình, để cho buổi bảo vệ luận án vui vẻ hơn ông quyết định chọn ra một nhóm người trong số các thính giả để chơi một trò chơi nhỏ làm tiền đề dẫn vào báo cáo nghiên cứu tiếp theo.

Các thính giả ngồi trong một khán phòng ~A~ gồm ~N~ dãy ghế mỗi gãy gồm có ~M~ ghế. Dr. Patel sẽ phát cho người ngồi ở vị trí ~i~, ~j~ một số nguyên dương ~C_{ij}~. Dr. Patel muốn chọn một số thính giả theo một hình chữ nhật từ vị trí ngồi ~(x, y)~ đến vị trí ngồi ~(u, v)~ sao cho, số lượng số ~C_{ij}~ mà Dr. Patel phát cho mỗi thính giả là số nguyên tố nhiều nhất và diện tích hình chữ nhật mà Dr. Patel chọn là nhỏ nhất.

Input

• Dòng đầu tiên gồm 1 số nguyên ~T~ là số bộ test ~(1 \leq T \leq 10)~.
• Ứng với mỗi test:
  • Dòng đầu tiên gồm 2 số ~N, M~ được phân tách bởi dấu cách ~(1 \leq N, M \leq 200)~.
  • ~N~ dòng tiếp theo, mỗi dòng gồm ~M~ số nguyên ~C_{ij}~ là số mà Dr. Patel phát cho thính giả ngồi ở vị trí ~(i, j)~ ~(1 \leq C_{ij} \leq 10^{18}, 1 \leq i \leq N, 1 \leq j \leq M)~.

Output

• Với mỗi test, in ra toạ độ ~(x, y)~ và ~(u, v)~ thoả mãn điều kiện đề bài, mỗi số trong toạ độ cách nhau bởi dấu cách.

Sample

Input #1

2
3 3
1 4 7
6 2 13
9 24 8
4 4
97 83 13 22
11 132 66 18
57 11 90 88
32 56 67 63

Output #1

Case #1: 1 2 2 3
Case #2: 1 1 4 3

Dr. Patel đang học tiếng Anh, chợt trong đầu nảy ra một ý tưởng về một ngôn ngữ cho riêng bản thân mình, Dr. Patel đã làm như sau.

Trong ngôn ngữ tiếng anh gồm các phụ âm và các nguyên âm, nguyên âm gồm các ký tự a, u, o, e và i, còn lại là phụ âm. Ngôn ngữ mới của Patel sẽ được chuyển từ tiếng Anh sang bằng cách tất cả các chữ cái thuộc nguyên âm sẽ đều nhân đôi ký tự của chúng.

Ví dụ: chuỗi ký tự ehlo finalist sẽ được chuyển thành eehloo fiinaaliist.

Dr. Patel đang tạo dựng từ điển nên cần một chương trình tốt để giúp việc chuyển đổi ngôn ngữ dễ dàng hơn. Cho một chuỗi ký tự ~S~ có độ dài ~N~ là chuỗi ký tự trong ngôn ngữ của Dr. Patel, hãy viết chương trình chuyển ngôn ngữ ấy về tiếng Anh.

Input

• Dòng đầu gồm số nguyên dương ~T~ là số bộ test ~(1 \leq T \leq 100)~.
• Ứng với mỗi bộ test:
  • Dòng đầu gồm số nguyên dương ~N~ ~(1 \leq N \leq 256)~ là độ dài của chuỗi ký tự ~S~.
  • Dòng thứ hai gồm chuỗi ký tự ~S~ có độ dài là ~N~ gồm các ký tự trong bảng chữ cái viết thường và khoảng trắng.

Output

• Với mỗi test in ra output là chuỗi ký tự ~S~ sau khi được chuyển từ ngôn ngữ Dr. Patel về tiếng Anh.

Sample

Input #1

3
18
eehloo fiinaaliist
25
lcoojbeegiinneercoonteest
24
tiimee liimiit eexceeeed

Output #1

Case #1: ehlo finalist
Case #2: lcojbeginnercontest
Case #3: time limit exceed

Dr. Patel vừa chứng minh được số nguyên ~K~ tố là một số ~N~ có số ước nhỏ hơn ~K~. Nhưng vì giới hạn tính toán của con người, nhưng Dr. Patel lại muốn giải quyết các bài toán lớn, hãy giúp Dr. Patel tính xem có bao nhiêu số là số nguyên ~K~ tố trong dãy ~A~.

Input

• Dòng đầu gồm 1 số nguyên ~T~ chứa ~(1 \leq T \leq 10)~.
• Ứng với mỗi test:
  • Dòng đầu gồm 1 số nguyên ~N, K~ ~(1 \leq N \leq 10^5, 1 \leq K \leq 100)~.
  • Dòng tiếp theo gồm ~N~ số nguyên ~A_i~ ~(1 \leq A_i \leq 10^6)~.

Output

• Với mỗi test in ra số lượng số nguyên ~K~ tố trong dãy ~A~.

Sample

Input #1

2
6 3
1 2 3 5 7 9
7 4
9 10 1 18 8 5 4

Output #1

Case #1: 5
Case #2: 4

Dr. Patel đang loay hoay nghiên cứu toán học để đạt được điểm cao nhất trong bài luận án của mình. Dr. Patel đang nghiên cứu như sau.

Với một số ~N~. Tìm số lượng số ~X~ thoả mãn:

• ~0 \leq X \leq N~.
• ~N + X = N \oplus X~.

(với phép toán ~\oplus~ là phép toán XOR trong các phép toán thao tác bit).

Ví dụ: Với ~N = 5~ ta có ~2~ giá trị của ~X~ là ~[0, 2]~ thoả mãn điều kiện trên.

• ~5 + 0 = 5,\ \ 5 \oplus 0 = 5~
• ~5 + 2 = 7,\ \ 5 \oplus 2 = 7~

Dr. Patel mời bạn về để nghiên cứu cùng ông ấy, hãy giúp ông ấy tính toán xem, với ~N~ có bao nhiêu giá trị của ~X~ thoả mãn điều kiện trên.

Input

• Dòng đầu tiên mỗi dòng chứa 1 số nguyên ~T~ là số bộ test ~(1 \leq T \leq 10^5)~.
• Ứng với mỗi test, mỗi dòng chứa 1 số nguyên dương ~N~ ~(1 \leq N \leq 10^{16})~.

Output

• Với mối test, in ra số lượng ~X~ thoả mãn yêu cầu đề bài.

Sample

Input #1

5
10
8
88
31
2

Output #1

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

Giải thích #1

Với trường hợp ~N = 10~, có ~4~ trường hợp ~X~ thoả mãn điều kiện đề bài:

• ~10 + 0 = 10,\ \ 10 \oplus 0 = 10~
• ~10 + 1 = 11,\ \ 10 \oplus 0 = 11~
• ~10 + 4 = 14,\ \ 10 \oplus 0 = 14~
• ~10 + 5 = 15,\ \ 10 \oplus 0 = 15~

Với trường hợp ~N = 2~, có ~2~ trường hợp ~X~ thoả mãn điều kiện đề bài:

• ~2 + 0 = 2,\ \ 2 \oplus 0 = 2~
• ~2 + 1 = 3,\ \ 2 \oplus 1 = 3~