Graceful Prime Decomposition

We want to express a positive integer $N$ as a sum of prime numbers. Let $G(N, K)$ denote the number of ways to decompose $N$ using primes $p_i$ that are less than or equal to $K$. That is, $N$ is written as a sum of primes:

$N = p_1 + p_2 + p_3 + \cdots + p_r, \quad (p_i \le K)$

Recall that the smallest prime is $2$.

This decomposition carries one extra rule. The graceful rule requires that every pair of adjacent primes be different, that is $p_i \ne p_{i+1}$ for all $i$. We call such a decomposition a Graceful Prime Decomposition (GPD), written compactly as $N = (p_1, p_2, p_3, \ldots, p_r)$.

Order matters: $2 + 5$ and $5 + 2$ are counted as two different decompositions.

For example, $G(7, 5) = 3$:

• $7 = 2 + 3 + 2 \rightarrow (2, 3, 2)$
• $7 = 2 + 5 \rightarrow (2, 5)$
• $7 = 5 + 2 \rightarrow (5, 2)$

and $G(5, 5) = 3$:

• $5 = 2 + 3 \rightarrow (2, 3)$
• $5 = 3 + 2 \rightarrow (3, 2)$
• $5 = 5 \rightarrow (5)$

Note that $7 = 2 + 2 + 3$ is not a valid GPD, because the adjacent pair $2 + 2$ is equal. Likewise $(2, 3, 2)$ is valid but $(3, 2, 2)$ is not. Compute $G(N, K)$ for the given integers $N$ and $K$.

The first line contains the number of test cases $T$. Each test case is a single line with two integers $N$ and $K$, where $2 \le N, K \le 50$.

For each test case, print a single integer $G(N, K)$ on its own line.