MZL's Border

Problem Description

As is known to all, MZL is an extraordinarily lovely girl. One day, MZL was playing with her favorite data structure, strings. MZL is really like $Fibonacci~Sequence$, so she defines $Fibonacci~Strings$ in the similar way. The definition of $Fibonacci~Strings$ is given below.

1. $fib_1 = b$
2. $fib_2 = a$
3. $fib_i = fib_{i - 1}fib_{i - 2},~i > 2$ For instance, $fib_3 = ab,~fib_4 = aba,~fib_5 = abaab$. Assume that a string $s$ whose length is $n$ is $s_1s_2s_3...s_n$. Then $s_is_{i + 1}s_{i + 2}s_{i + 3}...s_j$ is called as a substring of $s$, which is written as $s[i : j]$. Assume that $i < n$. If $s[1 : i] = s[n - i + 1 : n]$, then $s[1 : i]$ is called as a $Border$ of $s$. In $Borders$ of $s$, the longest $Border$ is called as $s$' $LBorder$. Moreover, $s[1 : i]$'s $LBorder$ is called as $LBorder_i$. Now you are given 2 numbers $n$ and $m$. MZL wonders what $LBorder_m$ of $fib_n$ is. For the number can be very big, you should just output the number modulo $258280327(=2 \times 3 ^ {17} + 1)$. Note that $1\leq T\leq 100,~1\leq n\leq 10^3,~1\leq m\leq |fib_n|$.

Input

The first line of the input is a number $T$, which means the number of test cases. Then for the following $T$ lines, each has two positive integers $n$ and $m$, whose meanings are described in the description.

Output

The output consists of $T$ lines. Each has one number, meaning $fib_n$'s $LBorder_m$ modulo $258280327(=2 \times 3 ^ {17} + 1)$.

Sample Input

2
4 3
5 5

Sample Output

1
2

Author

SXYZ

Source

2015 Multi-University Training Contest 5