Với mỗi xâu thập phân (xâu chỉ gồm toàn chữ số từ \(0\) tới \(9\)), bạn được thực hiện một trong hai thao tác sau bao nhiêu lần tùy ý:

1) Chuyển chữ số đầu xâu về cuối xâu. Ví dụ: \(0432 \to 4320\).

2) Chuyển chữ số cuối xâu về đầu xâu. Ví dụ: \(0432 \to 2043\).

Giá trị của một xâu thập phân là giá trị trong hệ thập phân mà nó biểu diễn, ví dụ xâu \(0023\) có giá trị \(23\), xâu \(0000\) có giá trị \(0\).

Với một xâu thập phân và một số nguyên dương \(n\) nhập vào, bạn hãy kiểm tra xem có thu được xâu thập phân có giá trị là bội của \(n\) từ hai thao tác trên hay không.

Đầu vào

Dòng đầu tiên chứa số tự nhiên \(t\) \((1 \le t \le 10)\), số lượng test con.

Mỗi test con gồm hai dòng được mô tả như sau:

• Dòng đầu tiên chứa một xâu thập phân độ dài không quá \(10^5\).
• Dòng thứ hai chứa số nguyên dương \(n\) \((1 \le n \le 10^9)\).

Đầu ra

\(t\) dòng, mỗi dòng chứa một kí tự - câu trả lời đối với một test: \(Y\) nếu có thể thu được xâu thập phân là bội của \(n\), \(N\) trong trường hợp còn lại.

Subtask

\(20\%\) số test xâu thập phân chứa không quá \(17\) kí tự.

\(20\%\) số test xâu thập phân chứa từ \(18 - 1000\) kí tự.

Ví dụ

Đầu vào:

3
01000
2
1111
2
522341
5

Đầu ra:

Y
N
Y

Giải thích: Xâu \(01000\) có giá trị \(1000\) là bội của \(2\) nên xuất ra \(Y\); xâu \(1111\) dù chuyển thế nào vẫn ra chính nó và xâu có giá trị lẻ, xuất ra \(N\); chuyển \(5\) về cuối ta được xâu \(223415\) có giá trị là bội của \(5\) nên xuất ra \(Y\).