Mô tả: Cho một số nguyên dương n, hãy sinh ra tất cả các xâu nhị phân độ dài n sao cho không có hai ký tự 1 đứng liền nhau.

Đầu vào: Một số nguyên n (1 ≤ n ≤ 15)

Đầu ra: Ghi ra tất cả các xâu nhị phân độ dài n thỏa mãn yêu cầu, mỗi xâu là một dòng.

Ví dụ:

Input:
3

Output:
000
001
010
100
101