문제

차원 택시 기하학에서 두 점 과 사이의 거리는 으로 정의된다. 이를 통해, 반지름이 인 차원 원의 부피를 택시 거리가 이하인 정수 격자점 개수로 정의할 수 있다.

차원 과 반지름 이 주어질 때 차원 원의 부피를 구해보자. 단, 답이 매우 커질 수 있으니 정답을 으로 나눈 나머지를 출력한다.

입력

첫째 줄에 테스트케이스의 수를 나타내는 정수 가 주어진다.

둘째 줄부터 개 줄마다 차원의 수 , 반지름 이 공백으로 구분되어 주어진다.

, 은 항상 정수이다.

출력

개 줄에 걸쳐 각 테스트케이스의 정답을 출력한다.