Frequency of character B in Fibonacci string and time limit exceed error

Consider the character string generated by the following rule:

• F[0] = "A"
• F[1] = "B"
• ...
• F[n] = F[n-1] + F[n-2] with n > 1

Given two positive integers n and k. Let's count the number of characters 'B' in the first k positions of string F[n].

I came up with this idea and got time limit exceeded error:

public class G_DemKyTuB {
    public static long[] F = new long[50];
    public static Scanner input = new Scanner(System.in);

    public static long count(int n, long k) {
        if (n == 0 || k == 0) return 0;
        else if (n == 1) return 1;
        else {
            if (k > F[n - 1]) return count(n - 1, F[n - 1]) + count(n - 2, k - F[n - 1]);
            else return count(n - 1, k);
        }
    }

    public static void main(String[] args) {
        F[0] = 1; F[1] = 1;
        for (int i = 2; i < 46; i++) F[i] = F[i - 2] + F[i - 1];
        int T = input.nextInt();
        while (T-- > 0) {
            int n = input.nextInt();
            long k = input.nextLong();
            System.out.println(count(n, k));
        }
    }
}

Can some one help me to improve time complexity? Seems my solution has O(n^2) time complexity.

Test case for this question: