SHARYGIN 2005 Problem 11

The square was cut into $n^2$ rectangles with sides $a_i \times b_j, i , j= 1,..., n$ . For what is the smallest $n$ in the set $\{a_1, b_1, ..., a_n, b_n\}$ all the numbers can be different?