문제

다음 조건을 만족하는 자연수를 베개 수라고 정의한다.

i) 각 자릿수는 , , , 중 하나이다.

ii) 숫자 는 번 이상 연속하여 등장하지 않는다.

예를 들어 12333221333이나 321은 베개 수이지만, 5122333이나 11은 베개 수가 아니다.

다음 쿼리를 처리하는 프로그램을 작성하라.

• x S: 로 시작하는 자리 베개 수의 가짓수를 로 나눈 나머지를 구해 출력한다.

입력

첫 번째 줄에 쿼리의 개수 가 주어진다.

두 번째 줄부터 개의 줄에 걸쳐, 각 줄마다 쿼리가 주어진다.

는 길이 이내의 , , , 로만 이루어진 문자열이다.

출력

쿼리가 주어질 때마다, 한 줄에 하나씩 쿼리의 답을 출력한다.