Biến đổi nhị phân

Với một dãy nhị phân bất kỳ, ta biến đổi dãy nhị phân như sau: mỗi chữ số của dãy được thay đồng thời theo quy tắc

• $1\to 01$
• $0\to 10$

Như vậy, với dãy bắt đầu là $1$, sau bước biến đổi thứ nhất, ta sẽ thu được dãy $01$. Sau phép biến đổi thứ $2$, ta thu được $1001$. Sau phép biến đổi thứ $3$, ta thu được $01101001$, ...

Người ta muốn tính xem, bắt đầu từ dãy $1$, sau $n$ bước biến đổi sẽ thu được dãy gồm có bao nhiêu cặp $2$ số $0$ đứng liên tiếp (tức là số vị trí $i$ mà chữ số thứ $i$ và chữ số thứ $i+1$ của dãy đều bằng $0$). Với $n=0$, dãy chỉ gồm một chữ số $1$.

Dữ liệu vào

Gồm một số test, mỗi test được ghi trên một dòng, mỗi dòng ghi một số nguyên không âm $n$. Dữ liệu kết thúc ở cuối file.

Dữ liệu ra

Với mỗi test, theo đúng thứ tự trong dữ liệu vào, ghi ra trên một dòng số cặp $2$ số $0$ đứng liên tiếp. Đáp án có thể rất lớn, cần in ra giá trị chính xác.

Ràng buộc

• $0\le n\le 1000$.
• Số test (số dòng) từ $1$ đến $1000$.

Subtasks

• Subtask 1 ($40\%$ số test): $n\le 20$.
• Subtask 2 ($40\%$ số test): $n\le 50$.
• Subtask 3 ($20\%$ số test): $n\le 1000$.

Ví dụ