Botas no podía pagar el alquiler de su cuarto por adelantado (lo asaltaron por el Alto) por N días. Tenía una barra de plata de N centímetros de largo; de modo que hizo el siguiente el siguiente arreglo con su casera. Le dijo que cortaría la barra en pedazos pequeños. El primer día le daría un centímetro de la barra de plata y cada día subsiguiente le agregaría otro centímetro más y ella conservaría la plata en prenda.

El podía cortar la barra en N centímetro para dárselas cada día, pero es un trabajo muy laborioso y botas es muy flojo para hacer ese trabajo pero su casera es muy desconfiada. El desea cumplir el acuerdo dividiendo la barra en el minino número posible de partes. Por ejemplo, podía darle a la casera un centímetro el primer día, otro centímetro el segundo día, y el tercer día podía entregarle uno de tres centímetros y ella le devolverá las dos partes de un centímetro, y así hasta cumplir con todos los días (Este solo es un ejemplo de como podría funcionar el acuerdo).

Tu trabajo es encontrar el mínimo número de cortes en la barra de tal forma que satisfaga el acuerdo de botas con su casera, así él le pagara y ella podrá devolverle los pedazos a fin de fecha.


La primera línea contiene el número de casos de prueba T, (0 ≤ T ≤ 100), las siguientes para cada caso de prueba se dará un N, que representa tanto al tamaño de la barra, como al número de días  (0 ≤ N ≤ 10^7).

Para cada caso de prueba usted debe imprimir el número minino de cortes de la barra, tal que se cumpla el acuerdo con la casera.