Số may mắn

Tại một diễn đàn Tin học, ban tổ chức tổ chức trò chơi bốc thăm nhận quà.

Mỗi người chơi bốc được một số nguyên dương \(N\). Sau đó ban tổ chức bốc thăm ngẫu nhiên một chữ số \(M\) \((1 \le M \le 9)\).
Với mỗi người chơi, ta thực hiện quá trình sau:

• Tính \(N_1\) là tổng các chữ số của \(N\).
• Tính \(N_2\) là tổng các chữ số của \(N_1\), v.v.

Lặp lại cho đến khi nhận được một số có đúng một chữ số. Nếu chữ số cuối cùng bằng \(M\) thì người chơi đó được xem là may mắn.

Hãy xác định với từng người chơi, họ có may mắn hay không.

Input

Dòng đầu chứa hai số \(K\) và \(M\) cách nhau bởi một dấu cách, trong đó \(K\) là số người chơi.

\(K\) dòng tiếp theo, dòng thứ \(i\) chứa số \(N\) của người chơi thứ \(i\).

Output

Ghi ra \(K\) dòng. Dòng thứ \(i\) ghi 1 nếu người chơi thứ \(i\) may mắn, ngược lại ghi 0.

Input

%
3 6
12345
6
123456789

Output

%
1
1
0

Scoring

• Có 50% số test với \(K \le 10^2\) và \(N \le 10^6\).
• Có 20% số test với \(K \le 10^3\) và \(N \le 10^9\).
• Có 30% số test với \(K \le 10^7\) và \(N \le 10^{100}\).