우아한 소수 분해

양의 정수 $N$을 소수들의 합으로 나타내려고 합니다. $G(N, K)$를 $K$ 이하의 소수 $p_i$만 사용해 $N$을 분해하는 경우의 수로 정의합니다. 즉, $N$을 다음과 같은 소수의 합으로 씁니다.

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

가장 작은 소수는 $2$임에 유의하세요.

이 분해에는 한 가지 추가 규칙이 있습니다. 우아한(graceful) 규칙은 서로 이웃한 두 소수가 항상 달라야 한다는 것으로, 모든 $i$에 대해 $p_i \ne p_{i+1}$ 이어야 합니다. 이런 분해를 우아한 소수 분해(Graceful Prime Decomposition, GPD) 라고 부르며, 간단히 $N = (p_1, p_2, p_3, \ldots, p_r)$로 표기합니다.

순서는 구별합니다. 예를 들어 $2 + 5$와 $5 + 2$는 서로 다른 분해로 셉니다.

예를 들어 $G(7, 5) = 3$입니다.

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

그리고 $G(5, 5) = 3$입니다.

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

$7 = 2 + 2 + 3$은 이웃한 $2 + 2$가 서로 같으므로 올바른 GPD가 아닙니다. 마찬가지로 $(2, 3, 2)$는 올바르지만 $(3, 2, 2)$는 올바르지 않습니다. 주어진 정수 $N$과 $K$에 대해 $G(N, K)$를 구하세요.

첫째 줄에 테스트 케이스의 개수 $T$가 주어집니다. 각 테스트 케이스는 두 정수 $N$과 $K$가 주어지는 한 줄로 이루어지며, $2 \le N, K \le 50$입니다.

각 테스트 케이스마다 $G(N, K)$의 값을 정수 하나로 한 줄에 출력합니다.