Migrated from Lutece 564 Jack and Rose

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Jack and Rose are fond of gaming. During the night on Titanic, Jack comes up with a new interesting game.

The game is designed for $2$ players so that he and Rose can compete in it. He draws $N$ slots in a row, and assigns a point to each slot. Then he puts his piece labeled with $A$ in the $1_{st}$ slot (the leftmost one) and Rose's piece labeled with $B$ in the $N_{th}$ slot (the rightmost one). Jack and Rose take turns to play. Each round, the player must move $A$ to the next slot to its right, or move $B$ to the next slot to its left. If both pieces are in the same slot, the game ends. (Please refer to sample for more details.)

Whenever $A$ or $B$ is moved to a new slot, the new slot's point will be added to Jack's or Rose's total point. Of course if the point is negative, the owner's total point will be decreased.

Initially, because $A$ is in the $1_{st}$ slot and $B$ is in the $N_{th}$ slot, Jack's point equals to the point of $1_{st}$ slot and Rose's equals to the point of $N_{th}$ slot. Now Jack wants to know, after the row of slots are drawn, whether or not he can get more points in total and beat Rose definitely. Both Jack and Rose will try their best.

Input

There will be multiple test cases. The first line of the input is an integer $T$ ($T \leq 100$) indicating the number of test cases.

For each test case an integer $N$ ($2 \leq N \leq 10000$) comes first in a single line representing the number of slots drawn in a row. The next line lists $N$ integers describing the point assigned to every slot.

Note these points will be limited in the range $[-10000, 10000]$.

Output

For each test case print Case #x: s in a single line, in which $x$ is the number of the test case starting from $1$, and s is a string. If Jack can definitely beat Rose, $s$ is win; if Jack is definitely a loser to Rose, $s$ is lose; otherwise $s$ is tie.

Samples

3
4
1 3 2 3
4
1 2 2 3
5
-1 -2 -1 -1 -1

Case #1: win
Case #2: tie
Case #3: lose

Note

For the first sample, both choose move his/her own piece. And Jack gets $1+3+2 = 6$, Rose gets $3+2 = 5$.

Resources

10th UESTC Programming Contest Preliminary