여행 - 똑똑 한 원숭이 (용 척 정리)

Problem Description
숲 속 에 바나나 나무 (무한 길이) 가 줄 지어 있 는데 원숭이 한 마리 가 그 나무 위 에 서 있다. 원숭이 는 점프 하기 전에 카드 한 장 을 뽑 아야 한다. 카드 에 A + 1 개의 자연수 가 적 혀 있 는데 그 중 마지막 으로 B 이다. 앞의 A 개 수 는 B 보다 작 을 수 밖 에 없고 카드 의 숫자 는 같 을 수 있다.원숭이 는 매번 점프 할 때마다 카드 에서 자연수 C 를 선택 한 다음 왼쪽으로, 오른쪽으로 C 그루 의 나 무 를 뛴다.원숭이 의 임 무 는 왼쪽 에 인접 한 바나나 나무 에 뛰 어 올 랐 을 때 위의 바 나 나 를 먹 을 수 있다 는 것 이다.
예 를 들 어 A = 2, B = 4 일 때 카드 (2, 3, 4) 에 대해 원숭이 는 바 나 나 를 먹 을 수 있다. 원숭이 는 먼저 왼쪽으로 세 그루 의 나 무 를 뛰 고 오른쪽으로 두 그루 의 나 무 를 뛰 어 넘 을 수 있다.카드 (2, 2, 4) 에 대해 서 는 원숭이 가 왼쪽 에 인접 한 바나나 나무 에 뛰 어 들 수 없다. 
A 와 B 가 확인 되면 모두 B ^ A 장의 다른 카드 가 있 을 수 있 습 니 다.문 제 는 이 모든 카드 중 원숭이 가 임 무 를 수행 할 수 있 는 카드 가 몇 장 이 냐 는 것 이다. 
Input
첫 번 째 줄 k 는 k 조 테스트 데이터 가 있 음 을 나타 낸다. k < = 100
2 번 부터 k + 1 줄 까지 줄 마다 두 개의 자연수 A 와 B 를 하나의 빈 칸 으로 나눈다 (A < = 10, B < = 20).
Output
총 k 줄, 각 줄 의 숫자 는 각 조 의 데 이 터 를 대표 하 며 원숭이 를 왼쪽 에 인접 한 바나나 나무의 카드 수로 뛰 어 넘 을 수 있 습 니 다.
Sample Input

3
2 3
4 8
5 13

Sample Output

8
3840
371292

문제 풀이: 매번 카드 에서 한 장 씩 뽑 기 때문이다. 즉, 모든 카드 는 횟수 제한 없 이 선택 할 수 있다.
면 x1 * ak [1] + x2 * ak [2] +... + xn * ak [n] + xn + 1 * m = 1
ak [1]... ak [n], m 사이 에는 반드시 상호 질 적 인 수가 있어 서 는 안 된다 는 것 을 알 수 있다.
그래서 우 리 는 먼저 부합 되 지 않 는 상황 을 구한다. 즉, ak [1]... ak [n], m 사이 의 두 가지 약 수 는 1 보다 크다.
그들 은 공 통 된 약 수 를 가지 고 있다.
2, 3, 5, 7...........................................................
그리고 공통 적 으로 2 약수 의 개 수 를 구하 세 요. 3 의 개 수 는... 등등. 하지만 겹 치 는 현상 을 빼 야 합 니 다. 예 를 들 어 6 의 개 수 를 빼 야 합 니 다.
이것 은 용 척 의 정 리 를 써 야 한다.