Tại một diễn đàn Tin học, để tạo không khí vui vẻ người ta tổ chức cho những người tham gia trò chơi bốc thăm để có cơ hội nhận được những phần quà từ Ban tổ chức, cách thức như sau:

Đầu tiên mỗi người tham gia được bốc thăm một mảnh giấy trong đó ghi một số nguyên dương \(N\) (\(N \le 10^{100}\)). Sau đó Ban tổ chức sẽ bốc thăm ngẫu nhiên một con số \(M\) (\(1 \le M \le 9\)). Mỗi người chơi sẽ cộng các chữ số của số \(N\) để được số \(N_1\), tiếp tục cộng các chữ số của \(N_1\) để được số \(N_2\)... quá trình cho đến khi nhận được một số có một chữ số. Nếu kết quả bằng \(M\) thì người chơi may mắn nhận được phần quà.

Em hãy lập trình để giúp những người chơi xác định ai là người may mắn trúng thưởng.

Input

• Dòng đầu tiên chứa hai số \(K\) và \(M\) cách nhau một dấu cách, trong đó \(K\) là số người bốc thăm (\(K \le 1000\)).
• Trong \(K\) dòng tiếp theo, dòng thứ \(i\) ghi một số \(N\) là con số mà người chơi thứ \(i\) bốc được.

Output

• Ghi ra \(K\) dòng, trong đó dòng thứ \(i\) ghi số \(1\) tương ứng với người chơi bốc được số may mắn, ngược lại ghi \(0\).

Example

3 6
12345
6
123456789

1
1
0

Scoring

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