33974번 - SCSC 문자열 놀이

문제

빈 문자열에서 시작해서, 알파벳 대문자 S 또는 C를 맨 오른쪽 끝에 추가하는 시행을 원하는 횟수만큼 반복하는 놀이를 하려고 한다.

놀이의 점수는 다음 규칙과 같이 계산된다.

• 처음에 빈 문자열만 있을 때의 점수는 0ドル$점이다.
• 점수가 $X$점인 상황에서, 문자열의 맨 오른쪽 끝에 S를 추가하면 점수가 2ドルX+S$점이 된다.
• 점수가 $X$점인 상황에서, 문자열의 맨 오른쪽 끝에 C를 추가하면 점수가 2ドルX+C$점이 된다.

시행을 원하는 횟수만큼 반복해서 만든 문자열이 SCSC를 연속된 부분 문자열로 가지면서 점수가 정확히 $N$점이 되는 경우의 수를 구하는 프로그램을 작성해 보자!

문자열이 SCSC와 정확히 일치하는 경우도 센다. 또한, 시행 횟수가 동일하더라도 만들어진 문자열이 다르다면 다른 경우로 센다.

입력

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

둘째 줄부터 $T$개의 줄에 걸쳐 정수 $N,ドル $S,ドル $C$가 공백으로 구분되어 주어진다. $(1 \leq N \leq {10}^{12};$ 1ドル \leq S, C \leq {10}^6)$

출력

각 테스트 케이스마다 한 줄에 하나씩, 시행을 원하는 횟수만큼 반복해서 만든 문자열이 SCSC를 연속된 부분 문자열로 가지면서 최종 점수가 $N$점이 되도록 하는 경우의 수를 출력한다.

제한

노트