문제

채완이가 좋아하는 성인 게임에는 칼 아이템이 있다.

칼의 칼날은 크기의 정사각형 개가 한 칸씩 맞물려 연결되어 있는 형태이다.

아래는 일 때의 칼날을 나타낸 그림이다.

칼날은 , 크기의 광석을 겹치지 않고 빈 칸이 없도록 적절히 붙여 만들 수 있다.

이 주어질 때 만들 수 있는 서로 다른 칼날의 개수를 구하는 프로그램을 작성하시오.

광석은 어떤 경우에도 모자라지 않을 만큼 충분히 존재한다.

, 크기의 광석은 각각 다음과 같고 회전시킬 수 있다.

입력

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

이후 개의 줄에 걸쳐 이 주어진다.

출력

각 테스트 케이스마다 만들 수 있는 서로 다른 칼날의 개수를 로 나눈 나머지를 출력하라.

노트

인 서로 다른 칼날은 아래 그림처럼 7개가 있다.

인 서로 다른 칼날은 아래 그림처럼 33개가 있다.