숫자 7보다 큰 자연수는 서로 다른 한개 이상의 소수의 합으로 표현을 할 수 있습니다. 

예를들면 18은 5 + 13 으로 18이 되지요.
하지만 이러한 조합이 한가지만 있는게 아닙니다. 18도 5 + 13 말고도 7 + 11도 됩니다.

사용했던 소수를 한번 이상 사용하지 않는다고 가정 했을 때, 입력된 숫자를 만들 수 있는 소수의 합은 몇가지가 있는지를 출력 해 주세요.

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

두 번째 줄부터는 7이상, 10,000 이하의 정수 하나가 T개 주어집니다.

만들 수 있는 방법의 수가 너무 많을 수 있으니, 입력된 숫자를 만들 수 있는 합의 갯수를 123,456,789 로 나눈 나머지를 출력해주세요.