n людей расставлены по кругу и пронумерованы числами от 1 до n. Начинается считалочка, в которой выбывает каждый второй до тех пор, пока не останется один - он и выживает. Пусть номер выжившего равен x. Запускаем считалочку с x людьми, расставленных по кругу. Пусть выживет человек с номером y. Запускаем считалочку с y людьми и так далее. Процесс заканчивается, когда номер выжившего совпадет с количеством людей в круге в текущем раунде.

Рассмотрим пример когда n = 5: после первого раунда выживет человек с номером 3. Поскольку он не последний в кругу, то запускаем второй раунд считалочки с 3 людьми. Теперь человек с номером 3 выживет. Процесс останавливается.

Входные данные

Первая строка содержит количество тестов. Каждый тест состоит из одной строки, содержащей целое число n (0 < n ≤ 30000).

Выходные данные

Для каждого теста вывести его номер, двоеточие, пробел и общее количество повторов (раундов, проведенных после окончания первой считалочки, в которой изначально по кругу расставлены n людей). Дальше вывести пробел и номер выжившего в последнем раунде.