정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노 (Polyomino)라고 부른다. N개의 정사각형을 붙여 하나의 폴리오미노를 만들 때 수직방향-단조(vertically monotone)인 폴리오미노를 만들 수 있는 가짓수가 몇 개나 되는지 세고 싶다. 다각형이 수직방향-단조라는 것은, 어떤 수평선도 이 다각형을 두 번 이상 교차하지 않을 때를 말한다.

예를 들어 아래 그림의 (a)는 맨 오른쪽 아래 정사각형이 다른 정사각형과 변을 완전히 맞대고 있지 않기 때문에 폴리오미노가 아니며 (b)는 두 개의 다각형이 꼭지점만을 맞대고 있으므로 폴리오미노가 아니다. (c)는 폴리오미노이지만 점선과 같은 수평선에 대해 두 번 교차하므로 수직 방향-단조가 아니다. (d) (e) (f)는 모두 7개의 정사각형으로 만들어진 수직방향-단조 폴리오미노이다.

그러면 N개의 정사각형으로 만들 수 있는 수직방향-단조 폴리오미노의 개수를 세는 프로그램을 작성하라.

입력의 첫 번째 줄에는 테스트 케이스의 수 T(1≤T≤50) 가 주어진다. 각 테스트 케이스는 각 줄에 하나의 정수 N(1≤N≤100)이 주어진다.

각 테스트 케이스마다 N개의 정사각형으로 만들 수 있는 수직방향-단조 폴리오미노의 수를 한 줄에 하나씩 출력한다. 단 폴리오미노의 수가 10,000,000 (1천만) 보다 클 경우 1천만으로 나눈 나머지를 출력한다.