Bạn đang cố gắng tính số tiếp theo trong một dãy \(S_n\) được tạo ra bởi một đoạn mã bí mật. Bạn biết rằng đoạn mã này được tạo theo quy trình sau:

Đầu tiên, với mỗi \(k\) từ \(0\) đến \(29\), chọn một số \(C_k\) nằm trong khoảng từ \(0\) đến \(10006\) (bao gồm cả hai đầu).

Sau đó, với mỗi số nguyên \(n\) từ \(0\) đến \(1,000,000,000\) (bao gồm cả hai đầu):

• Viết \(n\) ở hệ nhị phân.
• Lấy các số \(C_k\) ứng với mỗi bit \(k\) được bật (bằng 1) trong biểu diễn nhị phân của \(n\). Ví dụ, khi \(n=5\), các bit \(0\) và \(2\) được bật, nên \(C_0\) và \(C_2\) được chọn.
• Cộng các số \(C_k\) này lại với nhau, chia cho \(10007\), và lấy số dư làm kết quả cho \(S_n\).

Bạn sẽ được cho một chuỗi các giá trị liên tiếp của dãy \(S\), nhưng bạn không biết các số của mình bắt đầu từ vị trí nào trong dãy (mặc dù bạn biết rằng vẫn còn ít nhất một số nữa trong dãy), và bạn không biết các giá trị \(C_k\) nào đã được chọn khi tạo dãy.

Hãy tìm số tiếp theo trong dãy, hoặc xuất ra UNKNOWN nếu không thể xác định được từ dữ liệu đã cho.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(T\), số lượng bộ test trong file dữ liệu.

Với mỗi bộ test:

• Một dòng chứa số nguyên \(N\), số lượng phần tử của dãy \(S\) mà bạn có.
• Một dòng chứa \(N\) số nguyên cách nhau bởi dấu cách, nằm trong khoảng từ \(0\) đến \(10006\), là các phần tử đã biết của dãy.

Dữ liệu ra

Với mỗi bộ test, xuất ra một dòng chứa "Case #\(X\): \(Y\)" trong đó \(X\) là số thứ tự của bộ test (bắt đầu từ 1), và \(Y\) là số tiếp theo trong dãy, hoặc chuỗi UNKNOWN nếu không thể xác định được số tiếp theo.

Ràng buộc

• \(1 \le T \le 20\)

Phân nhóm

• Tập dữ liệu nhỏ (Test set 1 - Visible): \(1 \le N \le 5\)
• Tập dữ liệu lớn (Test set 2 - Hidden): \(1 \le N \le 1000\)

Đ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ụ

3
7
1 2 3 4 5 6 7
4
1 10 11 200
4
1000 1520 7520 7521

Case #1: UNKNOWN
Case #2: 201
Case #3: 3514

Nguồn

Google Code Jam 2008, Vòng bán kết châu Mỹ, bài Code Sequence.

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