Quy tắc biến đổi dãy nhị phân được mô tả như sau:

• $1 \rightarrow 01$
• $0 \rightarrow 10$

Bắt đầu với dãy ban đầu là $1$, chúng ta sẽ thực hiện các bước biến đổi theo quy tắc trên để tạo ra các dãy nhị phân mới.

1. Bước Biến Đổi Thứ $1$:

   • Dãy ban đầu: $1$
   • Áp dụng quy tắc: $1 → 01$
   • Kết quả: $01$

2. Bước biến đổi thứ $2$:

   • Dãy trước đó: $01$
   • Áp dụng quy tắc $\rightarrow$ Kết quả: $1001$

3. Bước biến đổi thứ $3$:

   • Dãy trước đó: $1001$
   • Áp dụng quy tắc $\rightarrow$ Kết quả: $01101001$

4. ... Áp dụng tương tự theo các bước biển đổi trên

Bạn hãy tính xem sau $n$ bước biến đổi sẽ thu được dãy gồm bao nhiêu cặp có $2$ số $0$ đứng liên tiếp.

Gồm một số kiểm thử, mỗi kiểm thử được ghi trên một dòng, mỗi dòng ghi một số nguyên $n$ không âm. $(n < 1000)$

Với mỗi dữ liệu đầu vào của kiểm thử, hãy in ra số cặp $2$ số $0$ đứng liên tiếp