On a circle are given the points $A_1, B_1, A_2, B_2, \cdots, A_9, B_9$ in this order. All the segments $A_iB_j (i, j=1, 2, \cdots, 9$ must be colored in one of $k$ colors, so that no two segments from the same color intersect (inside the circle) and for every $i$ there is a color, such that no segments with an end $A_i$, nor $B_i$ is colored such. What is the least possible $k$?