Problem: Heidi got one brain, thumbs up! But the evening isn't over yet and one more challenge awaits our dauntless agent: after dinner, at precisely midnight, the N attendees love to play a very risky game...

Every zombie gets a number ni (1 ≤ ni ≤ N) written on his forehead. Although no zombie can see his own number, he can see the numbers written on the foreheads of all N - 1 fellows. Note that not all numbers have to be unique (they can even all be the same). From this point on, no more communication between zombies is allowed. Observation is the only key to success. When the cuckoo clock strikes midnight, all attendees have to simultaneously guess the number on their own forehead. If at least one of them guesses his number correctly, all zombies survive and go home happily. On the other hand, if not a single attendee manages to guess his number correctly, all of them are doomed to die!

Zombies aren't very bright creatures though, and Heidi has to act fast if she does not want to jeopardize her life. She has one single option: by performing some quick surgery on the brain she managed to get from the chest, she has the ability to remotely reprogram the decision-making strategy of all attendees for their upcoming midnight game! Can you suggest a sound strategy to Heidi which, given the rules of the game, ensures that at least one attendee will guess his own number correctly, for any possible sequence of numbers on the foreheads?

Given a zombie's rank R and the N - 1 numbers ni on the other attendees' foreheads, your program will have to return the number that the zombie of rank R shall guess. Those answers define your strategy, and we will check if it is flawless or not.

Input

The first line of input contains a single integer T (1 ≤ T ≤ 50000): the number of scenarios for which you have to make a guess.

The T scenarios follow, described on two lines each: 

  * The first line holds two integers, N (2 ≤ N ≤ 6), the number of attendees, and R (1 ≤ R ≤ N), the rank of the zombie who has to make the guess. 
  * The second line lists N - 1 integers: the numbers on the foreheads of all other attendees, listed in increasing order of the attendees' rank. (Every zombie knows the rank of every other zombie.) 

Output

For every scenario, output a single integer: the number that the zombie of rank R shall guess, based on the numbers ni on his N - 1 fellows' foreheads.

Examples

Input

4
2 1
1
2 2
1
2 1
2
2 2
2


Output

1
2
2
1


Input

2
5 2
2 2 2 2
6 4
3 2 6 1 2


Output

5
2

Note

For instance, if there were N = 2 two attendees, a successful strategy could be: 

  * The zombie of rank 1 always guesses the number he sees on the forehead of the zombie of rank 2. 
  * The zombie of rank 2 always guesses the opposite of the number he sees on the forehead of the zombie of rank 1. 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
namespace fastExpress {
template <typename T>
inline T read() {
  T f = 1, x = 0;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}
template <typename T>
inline void write(T x) {
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
inline void print_char(T x, char ch) {
  write(x), putchar(ch);
}
template <typename T>
inline void char_print(char ch, T x) {
  putchar(ch);
  write(x);
}
template <typename T>
inline void print_space(T x) {
  print_char(x, ' ');
}
template <typename T>
inline void space_print(T x) {
  char_print(' ', x);
}
template <typename T>
inline void println(T x) {
  print_char(x, '\n');
}
template <typename T>
inline void lnprint(T x) {
  char_print('\n', x);
}
template <typename T>
inline void print_array_in_range1(T* a, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) print_char(a[i], " \n"[i == r]);
}
template <typename T>
inline void print_array_in_range2(T* a, int l, int r) {
  println(r - l + 1), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range3(T* a, int l, int r) {
  for (int(i) = (r); (i) >= (l); --(i)) print_char(a[i], " \n"[i == l]);
}
template <typename T>
inline void print_array_in_range4(T* a, int l, int r) {
  println(r - l + 1), print_array_in_range3(a, l, r);
}
template <typename T>
inline void print_array_in_range5(T* a, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) println(a[i]);
}
template <typename T>
inline void print_array_in_range6(T* a, int l, int r) {
  println(r - l + 1), print_array_in_range5(a, l, r);
}
template <typename T>
inline void print_array_in_range7(T* a, int l, int r) {
  for (int(i) = (r); (i) >= (l); --(i)) println(a[i]);
}
template <typename T>
inline void print_array_in_range8(T* a, int l, int r) {
  println(r - l + 1), print_array_in_range7(a, l, r);
}
template <typename T>
inline void print_array_in_range9(T* a, int l, int r) {
  print_space(r - l + 1), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range10(T* a, int l, int r) {
  print_space(r - l + 1), print_array_in_range3(a, l, r);
}
template <typename T>
inline void print_array_in_range11(T* a, int l, int r) {
  print_space(r - l + 1), print_array_in_range5(a, l, r);
}
template <typename T>
inline void print_array_in_range12(T* a, int l, int r) {
  print_space(r - l + 1), print_array_in_range7(a, l, r);
}
template <typename T>
inline void print_array_in_range13(T* a, int l, int r, int n) {
  println(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range14(T* a, int l, int r, int n) {
  println(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range15(T* a, int l, int r, int n) {
  println(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range16(T* a, int l, int r, int n) {
  println(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range17(T* a, int l, int r, int n) {
  print_space(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range18(T* a, int l, int r, int n) {
  print_space(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range19(T* a, int l, int r, int n) {
  print_space(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array_in_range20(T* a, int l, int r, int n) {
  print_space(n), print_array_in_range1(a, l, r);
}
template <typename T>
inline void print_array1(T* a, int n) {
  print_array_in_range1(a, 1, n);
}
template <typename T>
inline void print_array2(T* a, int n) {
  println(n), print_array1(a, n);
}
template <typename T>
inline void print_array3(T* a, int n) {
  print_array_in_range3(a, 1, n);
}
template <typename T>
inline void print_array4(T* a, int n) {
  println(n), print_array3(a, n);
}
template <typename T>
inline void print_array5(T* a, int n) {
  print_array_in_range5(a, 1, n);
}
template <typename T>
inline void print_array6(T* a, int n) {
  println(n), print_array5(a, n);
}
template <typename T>
inline void print_array7(T* a, int n) {
  print_array_in_range7(a, 1, n);
}
template <typename T>
inline void print_array8(T* a, int n) {
  println(n), print_array7(a, n);
}
template <typename T>
inline void print_array9(T* a, int n) {
  print_space(n), print_array1(a, n);
}
template <typename T>
inline void print_array10(T* a, int n) {
  print_space(n), print_array3(a, n);
}
template <typename T>
inline void print_array11(T* a, int n) {
  print_space(n), print_array5(a, n);
}
template <typename T>
inline void print_array12(T* a, int n) {
  print_space(n), print_array7(a, n);
}
template <typename T>
inline void vector_print(vector<T> a, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) print_char(a[i], " \n"[i == r]);
}
template <typename T>
inline void map_print(map<T, T> a, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) print_char(a[i], " \n"[i == r]);
}
template <typename T>
inline void stack_print(stack<T> a, char ch) {
  while (!a.empty()) print_char(a.top(), ch), a.pop();
}
template <typename T>
inline void queue_print(queue<T> a, char ch) {
  while (!a.empty()) print_char(a.front(), ch), a.pop();
}
template <typename T>
inline void pq_print(priority_queue<T> a, char ch) {
  while (!a.empty()) print_char(a.top(), ch), a.pop();
}
inline void print_string_in_range(string s, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) putchar(s[i]);
}
inline void print_chars_in_range(char* a, int l, int r) {
  for (int(i) = (l); (i) <= (r); ++(i)) putchar(a[i]);
}
inline void print_allstring(string s) {
  print_string_in_range(s, 0, (int)s.size() - 1);
}
inline void filein(string s) { freopen((s + ".in").c_str(), "r", stdin); }
inline void fileout(string s) { freopen((s + ".out").c_str(), "w", stdout); }
inline void file(string s) { filein(s), fileout(s); }
}  // namespace fastExpress
using namespace fastExpress;
int n, r;
int main() {
  int Test = read<int>();
  while (Test--) {
    n = read<int>(), r = read<int>();
    int sum = 0;
    for (int(i) = (1); (i) <= (n - 1); ++(i)) sum += read<int>();
    println((r - sum % n + n) % n + 1);
  }
}