Xâu Fibonacci thường được sử dụng để rèn luyện kỹ năng xử lý khi giới thiệu các giải thuật xử lý xâu. Xét dãy xâu F₀, F₁, F₂  , . . . xây dựng theo quy tắc sau:

• F₀ =’a’
• F₁ = ‘b’
• Fn = F_n-2 + F_n-1, n>1

Yêu cầu: Cho hai số nguyên n và k (0 ≤ n≤ 45, k không vượt quá độ dài xâu F_n). Hãy xác định số lượng ký tự a xuất hiện trong k ký tự đầu tiên của xâu F_n

Dữ liệu: Vào từ file FIB2.INP

• Dòng đầu ghi số nguyên T là số test cần xử lý (1 <= T <=100)
• Mỗi dòng trong T dòng sau ghi hai số n và k cách nhau ít nhất một dấu cách.

Kết quả: Kết quả ghi vào file văn bản FIB2.OUT, ứng với mỗi test trên một dòng dưới dạng một số nguyên.

Ví dụ: