Джон Сноу находится в поиске некоторых сфер, необходимых для победы над белыми ходоками. Существует k различных типов сфер, и ему нужна хотя бы одна сфера каждого типа. Одна сфера каждый день появляется у основания Чардрева на севере стены. Появление сферы каждого типа равновероятно. Так как север стены полон опасностей, он хочет знать минимальное количество дней, которое он должен ждать, посылая рейнджера собирать сферы каждый день, так что вероятность получения хотя бы одной сферы каждого типа как минимум 
, где ε < 10 - 7.
Для того, чтобы лучше подготовиться, он хочет знать ответ для q различных значений pi. Так как он занят планированием боевой стратегии с Сэмом, он просит вашей помощи.
Выходные данные
Выведите q строк. На i-й из них выведите единственное целое число — ответ на i-й запрос.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
1
|
1
|
|
2
|
2 2
1
2
|
2
2
|