Поймай бабочку
(Время: 1 сек. Память: 32 Мб Сложность: 51%)
Летом в деревне Алексей наблюдает как его сестра Аня ловит бабочек. Аня ловит бабочку и играет с ней после каждой поимки. Алексей заметил, что первую бабочку Аня поймала после минутной игры с сачком. Время игры перед ловлей (2×k)-й бабочки совпадает со временем игры перед ловлей k-й бабочки и на одну минуту меньше времени игры перед ловлей (2×k+1)-й бабочки. Бабочек так много, что Аня после игры мгновенно ловит новую бабочку.
Алексея заинтересовало три вопроса:
- Через сколько минут Аня поймает N-ю бабочку?
- Сколько бабочек поймала Аня до своей игры в N минут?
- Сколько бабочек поймала за N минут?
Входные данные
Входной файл INPUT.TXT содержит в первой строке натуральное число T – число вопросов.
Далее в T строках содержится по два числа Q и N – вид запроса и N. (1 ≤ T ≤ 104; Q = 1, 2, 3; 1 ≤ N ≤ 1010).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на каждый вопрос по модулю 998244353 через пробел.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
1 3
2 2
3 10 | 4 2 6 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
