Sử dụng hàng đợi (queue) để sinh ra N số nhị phân đầu tiên theo thứ tự từ 1 đến N.

Thuật toán:

1. Khởi tạo queue với số "1".
2. Lặp N lần: lấy số đầu queue, in ra, đồng thời đẩy hai số mới vào cuối: số đó nối thêm "0" và nối thêm "1".

Ví dụ: từ "1" sinh ra "10" và "11"; từ "10" sinh ra "100" và "101"; v.v.

Đầu vào

Một dòng duy nhất chứa số nguyên N (1 ≤ N ≤ 1000).

Đầu ra

In ra N dòng, mỗi dòng là một số nhị phân, theo thứ tự từ 1 đến N.

Ví dụ

Input:
5

Output:
1
10
11
100
101