Строки Фибоначчи --- 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$. В этот раз он поставил перед собой более сложную задачу --- необходимо найти, сколько раз буква <<a>> встречается среди первых $k$ символов строки $F_i$.

Напишите программу, решающую эту задачу.

Входной файл содержит несколько наборов входных данных. Первая строка входного файла содержит целое число $T$ наборов входных данных ($1 \le T \le 100$). Каждая из последующих $T$ строк описывает один набор входных данных и содержит по два целых числа: $n$ и $k$ ($0 \le n \le 45$, $1 \le k \le |F_n|$, как $|F_n|$ обозначена длина строки $F_n$, позиции символов в строке нумеруются с единицы).

Выведите в выходной файл $T$ строк, каждая из которых должна содержать одно число --- ответ для соответствующего набора входных данных.