상근이는 자신의 이름을 딴 방송국 GSK를 만들었다. GSK는 스포츠 전문 방송국으로 곧 열리는 경기 N개를 모두 취재하려고 한다.

각각의 스포츠 경기 E_i(1 ≤ i ≤ n)의 시작 시간은 s_i, 경기 시간은 d_i, 경기장은 g_i이다. g_i에서 g_j로 가는 이동 시간은 t_i,j(1 ≤ i,j ≤ n)이며, t_i,j = t_j,i와 t_i,j ≤ t_i,k + t_k,j (1 ≤ i,j,k ≤ n)을 만족한다.

리포터는 경기가 열리는 동안 그 경기장에서 계속 취재를 해야 한다. 즉, 한 리포터가 두 경기 E_i와 E_j를 취재하려면, s_i + d_i + t_i,j ≤ s_j 나 s_j + d_j + t_j,i ≤ s_i를 만족해야 한다.

경기 정보가 모두 주어졌을 때, 한 리포터가 동시에 취재할 수 없는 가장 큰 경기의 부분집합을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 경기의 수 n (1 ≤ n ≤ 1,000)이 주어진다. 둘째 줄에는 각 경기의 시작 시간 s_i, 셋째 줄에는 경기 시간 d_i가 주어진다. (1 ≤ s_i, d_i ≤ 1,000,000) 넷째 줄부터 총 n개 줄 중 i번째 줄에는 n-i+1개의 정수가 주어지며, t_i,i, t_i,i+1, ..., t_i,n을 나타낸다. (0 ≤ t_i,j ≤ 1,000,000) t_i,i는 항상 0이다.

출력 형식

각 테스트 케이스마다 두 줄을 출력한다. 첫째 줄은 한 리포터가 동시에 취재할 수 없는 가장 큰 경기의 부분집합의 크기 k이고, 둘째 줄에는 집합에 포함된 경기의 번호를 출력한다. (E_i에서 i) 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

예제 입력

2
3
7 8 9
1 1 1
0 2 2
0 1
0
2
7 12
3 2
0 2
0

예제 출력

3
2 3 1
1
2