#1475 · Biến đổi nhị phân

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