30824번 - 피보나치 더하기

두 양의 정수 $k$, $x$가 주어질 때, 피보나치 수열의 항들 중 정확히 $k$개를 더하여 $x$를 만들 수 있는지 판별하여라. 이때 피보나치 수열의 항을 중복하여 선택할 수 있다.

피보나치 수열이란, $F_1 = F_2 =1, F_n = F_{n-1} + F_{n-2}, (n \geq3)$로 정의되는 수열이다.

첫 번째 줄에 테스트케이스의 수 $T$가 주어진다. $(1 \leq T \leq 100)$

다음 $T$개의 줄에 사용할 피보나치 수열의 항의 개수 $k$과 만들고자 하는 양의 정수 $x$가 공백으로 구분되어 주어진다. $(1 \leq k \leq 3;\, 1 \leq x \leq 10^{16})$

$T$개 줄에 걸쳐 문제에 대한 해답을 출력한다.

$i$번째 줄에는 $i$번째 테스트케이스의 정답을 출력한다. $k$개의 피보나치 수열의 항들을 더하여 $x$를 만들 수 있다면 YES, 만들 수 없다면 NO를 출력한다.

문제의 입력이 int 자료형을 초과할 수 있다. 대신 long long 자료형 등을 사용하는 것을 권장한다.

출력 시 대소문자에 유의한다. Yes, yes 등은 정답으로 인정되지 않는다.