Bốc số

Nhân dịp năm mới Giáp Thìn, An tham gia lễ hội đầu năm thường niên của làng. Lễ hội có nhiều trò chơi thú vị thu hút sự chú ý của An, cậu chơi trò chơi đầu tiên là "Bốc số".

Luật chơi của trò chơi rất đơn giản: ở mỗi lượt chơi, An bốc từ thùng một lá thăm, mỗi lá thăm gồm 2 phần:

• Phần đầu lá thăm là một dãy có độ dài $N$ kí tự gồm các chữ số từ 1 đến 9.
• Phần sau lá thăm ghi số 0 hoặc 1, cách phần đầu một khoảng trống.

Công việc của An là xóa đi một hoặc một vài kí tự của phần đầu lá thăm sau đó viết các kí tự còn lại theo đúng thứ tự ban đầu (từ trái qua phải) để thu được một số nguyên dương lớn nhất thỏa mãn:

• Chia hết cho 5 nếu phần sau lá thăm là 0.
• Chia hết cho 3 nếu phần sau lá thăm là 1.

Yêu cầu: Hãy giúp An hoàn thành trò chơi.

Dữ liệu: Nhập từ tệp B2.INP có cấu trúc như sau:

• Dòng 1: Ghi số nguyên dương $t$ là số lần bốc thăm của An $(1 \le t \le 100)$.
• $t$ dòng tiếp theo, dòng thứ $i$ ghi một dãy có độ dài $N$ $(1 \le N \le 100)$ kí tự gồm các chữ số từ 1 đến 9 và một số $k$ (phân biệt bằng dấu cách trống) đại diện cho lá thăm thứ $i$.

Kết quả: Ghi ra tệp B2.OUT gồm $t$ dòng, dòng thứ $i$ chứa kết quả của lần bốc thăm thứ $i$ (dữ liệu đầu vào luôn đảm bảo có kết quả).

• 60% số test tương ứng 60% số điểm thoả mãn $k = 0$;
• 20% số test tương ứng 20% số điểm thoả mãn $1 \le N \le 18$;
• 20% số test tương ứng 20% số điểm không có ràng buộc gì thêm.