#1768 바닥왕 김타일

13  1 s   128 MB  

Description

안녕. 난 집공사의 감초 귀염둥이 인부 바닥왕 김타일이야. 화장실 바닥을 전설의 타일패턴으로 채우는 것이 내 꿈이지.

오늘은 수련의 일환으로 전설적인 바닥타일설치전문가 legend1x2 를 따라잡아볼거야. legend1x2 를 따라잡기 위해서는 다음과 같은 일을 해야 해. 가로로 W, 세로로 C ( 1 ≤ W ≤ 500 , 1 ≤ C ≤ 7) 길이의 화장실 바닥이 있어.
이 바닥을 1x2 모양의 타일로 빠짐없이 채워야 하거든. 단 1×2 타일은 회전시켜서 2×1 타일로도 사용할 수 있어.
난 자비로우니까. 내가 놓은 타일끼리는 겹치면 안되고. 놀라운 사실은, legend1x2 는 단지 바닥을 채우기만 하는것이 아니라 가능한 모든 패턴으로 한 번 씩 다 채워본다는거야. 그것도 1초안에!
내가 legend1x2 를 보면서 생각한 게 있는데, 난 안될거야...
그래도 가능한 모든 패턴이 몇 종류나 되는지 세는 것 정도는 1초안에 해볼 수 있지 않을까?

Input

입력의 첫 줄에는 테스트 케이스의 숫자 T(1 ≤ T ≤ 3, 500)가 들어온다.

각 테스트 케이스의 첫 줄에는 W, C(1 ≤ W ≤ 500, 1 ≤ C ≤ 7, W, C는 정수)가 들어온다.

Output

테스트 케이스별로 가능한 모든 패턴의 갯수를 “8888577” 로 나눈 나머지를 한 줄에 하나씩 출력한다.

Sample Input

Sample Output

2
1 2
2 2
1
2

Source

2011 Ajou University Programming Contest, Division 1