A3. Коллективный разум (сложная)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хайди наконец-то получила себе один мозг, порадуйтесь за неё! Однако, вечеринка ещё не окончена и новый вызов ожидает бесстрашного агента: после ужина, ровно в полночь, все n присутствующих сыграют в опасную игру...

Каждый зомби получает число ni (1 ≤ ni ≤ n), которое записывает у него на лбу. Хотя ни один из зомби не видит номера у себя на лбу, он видит то что написано на лбу каждого из n - 1 оставшихся. Обратите внимание, что числа не обязательно различны (они даже могут все совпадать). С этого момента, любая коммуникация между зомби запрещена. Наблюдение является единственной дорогой к успеху. Как только часы с кукушкой пробьют полночь, все присутствующие должны одновременно назвать номер, написанный у них на лбу. Если хотя бы один из них называет номер правильно, то все зомби выживают и счастливые уходят домой. С другой стороны, если никто из присутствующих не назовёт свой номер правильно, все они обречены на смерть!

Зомби вообще-то не очень умны, и Хайди не хочет рисковать своей жизнью, поэтому она быстро изучила украденный мозг и теперь может удалённо перепрограммировать стратегию принятия решения для каждого присутствующего на полуночной игре. Вам следует предложить Хайди стратегию, по которой хотя бы один из присутствующих всегда назовёт свой номер правильной, для любой последовательности чисел ni.

По данному рангу зомби и n - 1 числу ni на лбах остальных зомби ваша программа должна вернуть число, которое должен назвать зомби с рангом r. Эти ответы определяют вашу стратегию, а программа жюри проверит, является ли она безупречной.

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

В первой строке входных данных записано целое число t (1 ≤ t ≤ 50000): количество сценариев игры, для которых вам следует дать ответ.

Далее следуют t описаний сценариев, каждое состоит из двух строк:

  • В первой строке записаны два целых числа n (2 ≤ n ≤ 6) — количество присутствующих, и r (1 ≤ r ≤ n) — ранг зомби, который делает догадку.
  • Во второй строке записано n - 1 целое число — числа, написанные на лбу всех остальных присутствующих, перечисленные в порядке возрастания их рангов (каждый зомби знает ранги всех остальных зомби).
Выходные данные

Для каждого сценария выведите одно целое число: номер, который должен назвать зомби с рангом r, основываясь на данной информации о числах ni на лбах остальных n - 1 зомби.

Примеры
Входные данные
4
2 1
1
2 2
1
2 1
2
2 2
2
Выходные данные
1
2
2
1
Входные данные
2
5 2
2 2 2 2
6 4
3 2 6 1 2
Выходные данные
5
2
Примечание

К примеру, если всего присутствующих n = 2, то успешной стратегий является:

  • Зомби с рангом 1 всегда называет номер, который он видит на лбу зомби с рангом 2.
  • Зомби с рангом 2 всегда называет число, противоположное тому, что написано на лбу зомби с рангом 1.