10
1 2 3 1 1 1 1 1 1 1
2 3 4 1 1 1 1 1 1 1
3 4 5 6 1 1 1 1 1 1
1 1 6 7 8 9 1 1 1 1
1 1 1 8 1 10 1 1 1 1
1 1 1 9 10 11 12 1 1 1
1 1 1 1 1 12 13 14 15 1
1 1 1 1 1 1 14 15 16 1
1 1 1 1 1 1 15 16 17 1
1 1 1 1 1 1 1 1 1 18