#1021 Tales of Hiinaeq I : the legendary Amazon sage

82  1 s   128 MB  

Description

Through out many worlds, good and evil always exist, and it's no exception for the Amazon world. Amazon, the tribe only consisting of women, worshiping strength to survive as women this cruel and merciless world, is now confronting the huge problem, which might lead the tribe to be eliminated forever from the world. The case was begun with a cutest Amazon girl, Ryuju, releasing one of 12 seals, called Legend12, that the ancient, legendary Amazon sage Hiinaeq made to seal the world's every evil for the safety of Amazon. But do not worry. Hiinaeq is a legendary sage. Her wisdom, enough to seal the every evil in the world, foresaw such accident, and she left a scroll called ANSI(ANti-Sealed Instruction), contents the instructions of dealing against each released evils. The seal Ryuju broke, was the seal for calculation monster Kimgori. Kimgori, the evil sealed in third by Hiinaeq, somehow can convert this world into an integer sequence, and calculates the sum of them. Even cruel, he adds only the elements placed in odd place and only takes the remainder of his age from the summation result! That final result would be the key to the destruction of this world. Here, ANSI can tell you the way of converting this world into the integer sequence which is exactly the one Kimgori does. It can also tell you how old the monster is. Your job is to calculate the key faster than Kimgori, and tell Kimgori you were faster to reach the answer. Kimgori, the calculation monster with high pride, would ruin itself if you, the human with no special power, can calculate it faster than the monster. Remember, you are the only one who can stop the monster. Save the answer, save the world.

Input

First line, a number of test cases T(T<=1000) is given. Then for each test cases, first you would get two integer N, A, the number of sequence's elements(1<=N<=1000), followed by the age of Kimgori(1<=A<=1000000). After A, there would be n elements of the sequence, and each elements would be an integer number between 0 and 2147483647.

Output

Print one line for each cases, containing a number to save the world.

Sample Input

Sample Output

1
2 2
3
4
1