Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tags yet

No tag edit access

A3. Collective Mindsets (hard)

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputHeidi 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 *n*_{i} (1 ≤ *n*_{i} ≤ *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 *n*_{i} 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 *n*_{i} 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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2018 23:28:00 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|