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 phần quà từ Ban tổ chức. Cách thức như sau: Đầu tiên mỗi người tham gia bốc thăm một mảnh giấy trong đó ghi một số nguyên dương N (N ≤ 10¹⁰⁰). Sau đó Ban tổ chức sẽ bốc thăm ngẫu nhiên một con số M (1 ≤ M ≤ 9). Mỗi người chơi sẽ cộng các chữ số của số N để được số N1, tiếp tục cộng các chữ số của N1 để được N2,... Quá trình lặp lại cho đến khi nhận được một số có một chữ số. Nếu số kết quả bằng M thì người chơi may mắn nhận được phần quà.

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

Dữ liệu vào:

Tệp văn bản CAU3.INP gồm:

- Dòng 1: chứa hai số K và M (K ≤ 1000) cách nhau một dấu cách, trong đó K là số người bốc thăm.

- 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.

Kết quả:

Ghi vào tệp văn bản CAU3.OUT gồm K dòng, dòng thứ i ghi số 1 nếu người chơi thứ i may mắn, ngược lại ghi 0.

Ví dụ:

CAU3.INP
3 6
12345
6
123456789

CAU3.OUT
1
1
0

Ràng buộc:

- 50% số test: K ≤ 10², N ≤ 10⁶.
- 20% số test: K ≤ 10³, N ≤ 10⁹.
- 30% số test: K ≤ 10³, N ≤ 10¹⁰⁰.