$n \times m$ 크기의 행렬을 0과 1로 채워야 합니다. 이때 다음 조건을 만족해야 합니다.

• 가로 또는 세로로 연속해서 같은 숫자가 4개 이상 놓일 수 없습니다.
• 1로 채워진 셀들은 하나의 연결된 영역을 형성해야 합니다. (두 셀이 변을 공유하면 인접하다고 합니다. 셀들의 그룹은 그 그룹 내의 모든 두 셀 쌍에 대해, 그룹 내에만 머무르면서 인접한 셀로만 이동하여 두 셀을 연결하는 경로가 존재할 때 연결되었다고 합니다.)

위 조건을 만족하면서 1의 개수가 최대가 되는 행렬을 구성하세요. 1의 최대 개수와 해당 행렬을 출력하세요.

입력

첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 10^3$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 $n, m$ ($2 \le n, m \le 10^3$)이 주어집니다.

모든 테스트 케이스에 대한 $n \cdot m$의 합은 $10^6$을 넘지 않음이 보장됩니다.

출력

각 테스트 케이스마다 첫 번째 줄에 1의 최대 개수를 출력합니다. 그 다음 $n$개의 줄에 걸쳐 행렬을 출력합니다. 만약 여러 개의 해가 존재한다면, 그중 아무거나 출력해도 됩니다.

예제

입력 1

3
2 2
3 4
3 8

출력 1

4
11
11
9
1110
1110
1110
18
11101110
10111011
11011011