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\mathrm{\%}$ số test xâu thập phân chứa không quá $17$ kí tự.

$20\mathrm{\%}$ 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$.