철수, 영희, 지수 세 사람은 주사위를 사용한 게임을 하려고 한다. 철수-영희-지수 순서로 한 라운드씩을 반복하며 진행하며 첫 라운드는 철수가 시작한다. 주사위 게임은 다음과 같은 규칙으로 진행된다.

그림 1. 세 사람이 게임에 사용하는 8면 주사위의 전개도. 1에서 8사이의 자연수가 하나씩 기록되어 있다.

• [규칙 1] 각 라운드에 자신의 차례인 사람은 주사위를 굴린 후 윗면에 나타난 숫자를 기록한다.
• [규칙 2] 1라운드와 2라운드에는 별도로 패배 규칙을 적용하지 않는다.
• [규칙 3] 주사위를 굴린 사람은 이전 두 라운드와 현재 라운드를 포함한 총 세 라운드에서 주사위가 나타낸 숫자들의 합을 점수로 가진다.
• [규칙 4] 어떤 라운드에서 차례인 사람이 획득한 점수가 M점보다 작다면 해당 차례 사람은 게임에서 패배한다. 그리고 게임은 종료된다.

 예를 들어서 처음 두 라운드에 철수와 영희의 주사위가 차례로 4, 7를 나타냈다고 가정하자. 세 번째 라운드에 지수의 주사위가 4를 나타냈다면 지수는 총 15점을 획득한다. 만약 M이 15보다 큰 값이었다면 이 순간 지수는 패배하게 되고 게임은 종료될 것이다. 그렇지 않다면 지수는 15점을 획득하고 게임을 속행하게 된다. 세 친구들은 이 게임이 오랫동안 지속될 수 있는지 궁금해졌다.

 위와 같은 규칙대로 게임을 진행해나간다고 할 때, N번째 라운드의 주사위를 굴렸을 때에도 게임이 종료되지 않을 수 있는 경우의 수를 계산하시오. 단, 경우의 수를 1,000,000,007로 나눈 나머지만을 출력한다.

입력 형식

 첫 줄에는 테스트케이스의 수를 나타내는 30이하의 자연수 T가 주어진다. 이후 총 T개의 테스트케이스에 대한 입력이 차례로 주어진다.

 각 테스트케이스에 대한 입력은 한 줄에 공백으로 구분된 두 개의 자연수로 주어진다.

• 두 개의 자연수가 N M 형식으로 주어진다.
• N은 경우의 수를 계산할 마지막 라운드의 번호를 나타내는 1이상 10만이하의 자연수다.
• M은 각 라운드에 최소로 획득해야 할 점수를 나타내는 1이상 24이하의 자연수다.

출력 형식

 각 테스트케이스에 대한 정답을 한 줄에 하나씩 출력한다. 

• N번째 라운드까지 아무도 패배하지 않고 게임을 진행할 수 있는 경우의 수를 출력한다.