전화번호의 다이얼은 대부분 아래와 같이 생겼습니다.

걸기 쉬운 전화번호는, 전화번호가 서로 인접해 있는 번호들로 이어져 있을 때 이를 걸기 쉬운 전화번호 라고 합니다. 같은번호가 연속되어있는 999 같은 번호는 쉬운 번호가 아닙니다.

1256 같이 상/하/좌/우 로 이어져 있는 번호로 누를 수 있을 때 걸기 쉬운 전화번호 라고 합니다.

1252 같이 눌렀던 번호를 또 누를 수도 있습니다.

1569 는 1에서 5로가기 위해서 대각으로 가야하기 때문에 누르기 쉽지 않습니다.

길이가 L인 걸기 쉬운 전화번호가 몇가지 있는지 구해주세요.

첫 줄에는 테스트 케이스 T (1 <= T <= 100) 이 주어 집니다.

둘째 줄 부터는 전화번호의 길이 L (1 <= L <= 100) 이 주어집니다.

각 테스트에 대해 답을 한줄에 하나씩 출력 합니다. 단, 답이 클 수 있으므로 1,000,000,007 로 나눈 나머지를 출력 해 주세요.