Bài toán 3

Một chuỗi nhị phân (binary string) là một chuỗi chỉ chứa các ký tự ~0~ và ~1~. Với một chuỗi nhị phân ~t~ bất kỳ, gọi ~f(t)~ là số dãy con khác rỗng của ~t~ chỉ chứa ký tự ~0~, và gọi ~g(t)~ là số dãy con khác rỗng của ~t~ có chứa ít nhất ~1~ ký tự ~1~, e.g., ~f(000) = 7, g(100) = 4~. Định nghĩa "oneness" của chuỗi nhị phân ~t~ bởi ~O(t) := |f(t) - g(t)|~. Cho một số nguyên dương ~n~. Tìm chuỗi nhị phân nhỏ nhất và chuỗi nhị phân lớn nhất theo thứ tự từ điển có chiều dài ~n~ sao cho oneness của nó nhỏ nhất có thể.

Input. Dòng 1 chứa một số nguyên dương ~1 \le t \le 10^4~ là số bộ test. Mỗi bộ test gồm 1 dòng duy nhất chứa 1 số nguyên ~n~ (~1 \le n \le 2 \cdot 10^5~) – chiều dài của chuỗi nhị phân ~s~.

Output. In ra giá trị nhỏ nhất của oneness, chuỗi nhị phân nhỏ nhất và chuỗi nhị phân lớn nhất theo thứ tự từ điển có chiều dài ~n~ ứng với giá trị nhỏ nhất đó, cách nhau bởi 1 khoảng trắng.

Sample Input

3 
1 
2
3

Sample Output

1 0 1
1 01 10
1 001 100