피보나치 문자열 2

수학에서는 점화식이 자주 쓰인다. 보통 수열을 정의하는 데 쓰지만, 문자열의 수열을 정의하는 데에도 쓸 수 있다.

점화식으로 정의되는 문자열의 예로 피보나치 문자열 $F_0$, $F_1$, $\ldots$이 있다. 이 문자열은 다음과 같이 정의된다. $F_0=a$, $F_1=b$, $F_i=F_{i-2}F_{i-1}$ ($i > 1$). 처음 일곱 개의 피보나치 문자열은 a, b, ab, bab, abbab, bababbab, abbabbababbab이다.

디마는 알고리즘 동아리에서 문자열 알고리즘을 공부하고 있으며 피보나치 문자열을 최근에 알게 되었다. 그는 i가 커질수록 문자열의 길이가 매우 빠르게 늘어나서, $F_i$의 모든 문자를 구하려면 메모리가 너무 많이 필요하다는 것을 알았다. 지난번에는 $F_i$의 일부 문자만 구하는 문제를 풀었다. 이번에는 더 어려운 문제에 도전한다. $F_i$의 처음 $k$개 문자 중 문자 a가 몇 번 나타나는지 구해야 한다.

이 문제를 푸는 프로그램을 작성하라.

첫 줄에 테스트 데이터의 개수 $T$ ($1 \le T \le 100$)가 주어진다. 이어지는 $T$개 줄에는 각각 정수 $n$과 $k$ ($0 \le n \le 45$, $1 \le k \le |F_n|$)가 주어진다. 여기서 $|F_n|$은 문자열 $F_n$의 길이이며, 문자의 위치는 1부터 번호를 매긴다.

$T$개 줄에 걸쳐 각 테스트 데이터의 답을 한 줄에 하나씩 출력한다. 답은 $F_n$의 처음 $k$개 문자 중 a의 개수이다.