Fibonacci Strings 2

Recurrence relations are often used in mathematics. They usually define numerical sequences, but they can also define sequences of strings.

One example of strings defined by a recurrence is the Fibonacci strings $F_0$, $F_1$, $\ldots$ They are defined as follows: $F_0=a$, $F_1=b$, $F_i=F_{i-2}F_{i-1}$ for $i > 1$. The first seven Fibonacci strings are a, b, ab, bab, abbab, bababbab, and abbabbababbab.

Dima attends an olympiad programming club and is interested in string algorithms. He recently learned about Fibonacci strings. He quickly realized that their length grows very fast as i increases, so finding all characters of $F_i$ requires too much memory. Last time he only looked for some characters of $F_i$. This time he set himself a harder task: count how many times the letter a appears among the first $k$ characters of $F_i$.

Write a program that solves this problem.

The first line of the input contains the number of test cases $T$ ($1 \le T \le 100$). Each of the next $T$ lines contains two integers $n$ and $k$ ($0 \le n \le 45$, $1 \le k \le |F_n|$), where $|F_n|$ is the length of the string $F_n$. Character positions are numbered from 1.

Print $T$ lines. Each line contains one number, the answer for the corresponding test case: the number of a characters among the first $k$ characters of $F_n$.