Câu 2 (5.0 điểm). 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 sao cho 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.

Input

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) đại diện cho lá thăm thứ \(i\).

Output

Ghi ra tệp B2.INP gồm \(t\) dòng, dòng thứ \(i\) chứa kết quả của lần bốc thăm thứ \(i\). Nếu không có kết quả thì in ra \(-1\).

Example

4
2433514 0
5295284 0
12324524 1
5321 1

24335
5295
1324524
531

Scoring

• \(60\%\) số test thỏa mãn \(k = 0\).
• \(20\%\) số test thỏa mãn \(k = 1\) và \(N \le 18\).
• \(20\%\) số test không có ràng buộc gì thêm.