피보나치 문자열

수학에서는 점화식이 자주 쓰인다. 보통 수열을 정의할 때 쓰지만, 문자열의 수열을 정의하는 데에도 쓸 수 있다. 점화식으로 정의되는 문자열의 예로 피보나치 문자열 $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$의 $k$번째 문자를 구하는 프로그램을 작성하라.

입력 파일에는 여러 개의 테스트 케이스가 있다. 첫 줄에는 테스트 케이스의 개수 $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$개의 줄을 출력한다. 각 줄에는 해당 테스트 케이스의 답인 문자 하나만 출력한다.