Quién mató a Mickey Mouse?

A la taula tenim 8 pots iguals. Tots contenen un líquid innocu, tret d’un que conté verí per a ratolins. Se sap, a més, que si un ratolí beu aquest verí, mor exactament als 10 minuts.

Hem de trobar el pot amb verí. Disposem exactament de 10 minuts per trobar-lo, no tenim més temps.

Evidentment, amb 8 ratolins podríem saber-ho, ja que li donem a cada ratolí a veure d’un pot diferent i simplement esperem ... 10 minuts ... i tindrem la resposta de quin pot és el del verí. Però ... es pot fer amb menys pots (barrejant-los quan li donem als ratolins per beure?).

Per exemple, amb 4 pots (p1,p2,p3,p4)... basten 2 ratolins, ja que podem preparar dues mostres (p1+p3, p2+p3) ...pensa una mica.

Quants ratolins necessitem com a mínim per trobar el pot del verí?

Entrada

L’entrada comença amb un valor enter que indicarà el número de casos de prova.

Per cada cas de prova, indicarà el número de pots sobre el que hem de trobar aquell que te el verí.

Sortida

Per cada cas de prova s’indicarà el mínim número de ratolins necessaris per trobar el verí en 10 minuts.

Exemple d'Entrada

7
4
8
9
16
31
32
33

Exemple de Sortida

2
3
4
4
5
5
6