Розглянемо список цілих чисел . Спочатку містить цілі числа від до , кожне рівно один раз (але може містити кілька копій деяких цілих чисел). Порядок елементів у не важливий. Вам слід виконати наступну операцію разів:
Виберіть два елементи зі списку, нехай це будуть та . Вони можуть бути рівними.
Видаліть вибрані елементи з .
Додайте число у .
В кінці містить одне ціле число. Знайдіть максимальне значення цього цілого числа. Оскільки відповідь може бути великою, обчисліть її за модулем .
Перший рядок містить кількість тестів . Кожен із наступних рядків містить одне ціле число .
Для кожного тесту виведіть одне ціле чило — максимальне можливе значення останнього числа у списку, обчислене за модулем .