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 F0, F1, F2 , . . . xây dựng theo quy tắc sau: F0 =a F1 = b Fn = Fn-2 + Fn-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 Fn). 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 Fn 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.