#1980 기식왕 류기식

35  2 s   128 MB  

Description

 

아주대학교 내에 있는 산학원(산에 있는 학원)에서 서식 중인 평범한 잉간(잉여 인간)이다. 그의 하루의 유일한 즐거움은 식사 시간을 기다리는 것이다. 사실 밥 먹는 것 밖에 하는 일이 거의 없다고 봐도 무방하다.
어찌되었건 제한된 점심시간 안에서 식사를 해결하기 위해서는 주로 산학원에서 가장 가까운 기숙사 식당을 이용할 수 밖에 없는 형편이다.
하지만 최근 들어서 기숙사 식당의 극악무도한(예를 들어 치킨마요라든지, 치킨마요라든지)
식단에 류주는 분노할 수 밖에 없다. 기숙사 식당의 횡포에 맞서기 위해서 그는 기숙사 식당에 잠입하여 식단을 조작하기로 한다.
식단은 자물쇠가 걸린 금고에 보관되어 있는데 자물쇠는 N 자리의 숫자를 입력하는 자물쇠이다.
류주는 APC(Association of Professional Chicken) 측으로부터 각 자리 수에 들어갈 수 있는 숫자의 최대값을 입수했다. 그러나 그 이상의 정보의 입수는 잉간인 류주에는 힘든 일이었다.
그에게는 근성 밖에 없으므로 가능한 모든 숫자를 다 입력해보기로 한다. 류주가 입력해봐야 할 모든 비밀번호의 경우를 출력해주는 프로그램을 작성해주자.

Input

 

첫 줄에는 테스트케이스의 수가 들어온다.
각 테스트케이스에 첫 줄에는 자물쇠 비밀번호의 자리 수 N(1 ≤ N ≤ 6)이 입력되고 다음 줄에는 첫 번째 자리부터 N 번째 자리의 비밀번호의 최대 값 Xi(0 ≤ Xi ≤ 9)가 빈 칸을 구분으로 하여 한 줄에 입력된다.

Output

 

각 테스트 케이스에 대하여 가능한 모든 자물쇠 비밀번호를 사전 순으로 오름차순으로 하여 한 줄에 하나씩 모두 출력한다. 예제 출력을 참고한다.

Sample Input

Sample Output

1
3
1 2 2
0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
0 2 0
0 2 1
0 2 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
1 2 0
1 2 1
1 2 2

Source

Ajou Programming Contest, Division 1