Folkior

There is a set of tickets numbered from 1 to 30 (numbers can repeat). Each student drew one ticket. The teacher can perform the following operation: read out a list of several (possibly one) numbers and ask their owners to raise their hands. How many times does he need to perform this operation to find out the number of each student? (There are not necessarily 30 students.)

#
We will encode the tickets with binary numbers from 00001 to 11110. On the $k$-th stage, the teacher includes in the list all numbers whose $k$-th bit is one (for example, on the 3rd stage, the numbers are $4,5,6,7,12,13,14,15,20,21,22,23$, $28,29,30$). After the fifth stage, the teacher learns the binary code of the numbers from all students.

Four stages are insufficient even for one student: the number of their "possible" numbers after each stage (if the teacher is "unlucky") can decrease by no more than half.

## Problem