Ducci Sequence

Interview

Time limit1sMemory limit128 MB

Summary

Repeatedly replace each entry with the absolute difference of adjacent entries and report whether the tuple reaches all zeros or loops.

Level: Easy3 of 10
Topics: Simulation, Hash map
Solved: No attempts yet

Problem

A Ducci sequence is a sequence of integer n-tuples. Given an integer n-tuple $(a_1, a_2, \dots, a_n)$ , the next tuple in the sequence is formed from the absolute differences of adjacent entries, where the last entry $a_n$ is treated as adjacent to the first entry $a_1$ .

$(a_1, a_2, \dots, a_n) \rightarrow (|a_1 - a_2|, |a_2 - a_3|, \dots, |a_n - a_1|)$

Every Ducci sequence eventually reaches the all-zero tuple or falls into a periodic loop. For example, the sequence starting from $(8, 11, 2, 7)$ reaches the all-zero tuple after 5 steps.

$(8,11,2,7) \rightarrow (3,9,5,1) \rightarrow (6,4,4,2) \rightarrow (2,0,2,4) \rightarrow (2,2,2,2) \rightarrow (0,0,0,0)$

By contrast, the sequence starting from $(4, 2, 0, 2, 0)$ never reaches the all-zero tuple and instead enters a periodic loop. Notice below that the tuple $(0, 0, 0, 2, 2)$ recurs.

$\begin{gathered}(4,2,0,2,0) \rightarrow (2,2,2,2,4) \rightarrow (0,0,0,2,2) \rightarrow (0,0,2,0,2) \rightarrow (0,2,2,2,2) \rightarrow (2,0,0,0,2) \\ \rightarrow (2,0,0,2,0) \rightarrow (2,0,2,2,2) \rightarrow (2,2,0,0,0) \rightarrow (0,2,0,0,2) \rightarrow (2,2,0,2,2) \rightarrow (0,2,2,0,0) \\ \rightarrow (2,0,2,0,0) \rightarrow (2,2,2,0,2) \rightarrow (0,0,2,2,0) \rightarrow (0,2,0,2,0) \rightarrow (2,2,2,2,0) \rightarrow (0,0,0,2,2) \rightarrow \cdots\end{gathered}$

Given an n-tuple, write a program that determines whether the Ducci sequence starting from it reaches the all-zero tuple or falls into a periodic loop.

Input

The first line contains the number of test cases $T$ . Each test case consists of two lines: the first line contains the tuple size $n$ ( $3 \le n \le 15$ ), and the second line contains $n$ integers separated by spaces. Each integer is between 0 and 1000 inclusive. The number of steps needed for a Ducci sequence to reach the all-zero tuple or enter a loop does not exceed 1000.

Output

For each test case, print the answer on its own line. Print LOOP if the Ducci sequence falls into a periodic loop, or ZERO if it reaches the all-zero tuple.

Examples1

Example 1

Input

4
4
8 11 2 7
5
4 2 0 2 0
7
0 0 0 0 0 0 0
6
1 2 3 1 2 3

Expected output

ZERO
LOOP
ZERO
LOOP