Test 3 failed
Input:
1
5 8
3 5
2 4
1 5
3 4
1 2
1 3
2 5
1 4
Expected:2
2 1 2 2 1 2 1 2
Got:2
1 2 1 1 2 1 2 1