헬기 착륙장

건물 옥상에 헬리콥터가 착륙할 수 있도록 헬기 착륙장을 만들려고 한다.

헬기 착륙장은 아래와 같은 조건들을 모두 만족해야 한다.

• 헬기 착륙장은 $ k $ ($ k \ge 1 $)개의 동심원들로 구성된다.
• 헬기 착륙장을 구성하는 각 원의 반지름은 $ 1 $, $ 2 $, $ \ldots $, $ k $ ($ 1 $ 이상 $ k $ 이하의 서로 다른 자연수)이다.
• 각 원의 둘레는 한 가지 색의 페인트로 색칠되어야 한다.

헬기 착륙장의 크기란 동심원 중 반지름이 가장 큰 원의 반지름이며, 위의 조건에서 동심원의 개수 $ k $와 같음을 알 수 있다.

두 헬기 착륙장이 서로 다르다는 것은, 착륙장의 크기가 서로 다르거나, 크기는 같지만 동심원에 칠해진 색의 조합이 다른 것을 의미한다.

반지름이 $ r $인 원의 둘레를 색칠하기 위해서는 정확히 $ r $통의 페인트가 필요하다.

예를 들어, 빨강 페인트가 3통, 파랑 페인트가 4통 있을 때, 이 페인트를 이용하여 만들 수 있는 서로 다른 헬기 착륙장은 아래 그림에서 보인 것처럼 9가지가 있다. X 표시는 동심원의 중심을 나타낸다.

참고로, 크기가 3인 착륙장 중 아래 그림에서 보인 것처럼 그리려면 빨강 페인트 4=1+3통, 파랑 페인트 2통이 필요한데, 주어진 빨강 페인트 3통으로는 부족하므로 이와 같은 착륙장은 만들 수 없다.

현재 당신은 빨강 페인트 $ a $통과 파랑 페인트 $ b $통을 갖고 있다. 이들만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 개수를 $ 10^9 + 7 $로 나눈 나머지를 구하는 프로그램을 작성하라.

하나의 입력에서 $ T $개의 테스트 케이스를 해결해야 한다.

• 주어지는 모든 수는 정수이다.
• $ 1 \le T \le 10\,000 $
• $ 1 \le a, b \le 50\,000 $

1. (3점) $ T = 1 $. $ a, b \le 6 $.
2. (17점) $ T = 1 $. $ a, b \le 100 $.
3. (21점) $ T = 1 $. $ a, b \le 1\,000 $.
4. (23점) $ T = 1 $. $ a, b \le 5\,000 $.
5. (26점) $ T = 1 $.
6. (10점) 추가 제약 조건 없음.

첫 번째 줄에는 테스트 케이스의 수 $ T $ 가 주어진다.

다음 $ T $개의 줄에는 테스트 케이스들이 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $ a $와 $ b $가 공백 하나를 사이로 두고 주어진다.

각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 $ a $통과 파랑 페인트 $ b $통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 $ 10^9 + 7 $로 나눈 나머지를 출력한다.