Sereja likes to generate pseudo random binary sequences. Now Sereja has two generators: one is a based on linear congruential generators (LCGs) and another is based on Xorshift.

Sereja has some binary sequences generated in past times, and he wants to know which generator makes these sequences. You can know the details of Sereja's generators, then can you answer this problem?

The following is the details. We may give the length N and a seed integer S to the generators, then they generate a binary sequence A[1], A[2], ..., A[N].

The 1st generator works as follows (C++ code. If you are not familiar with C++, please see the below section Notes for C++):

/* ------------------ start here ---------------------*/ unsigned X; // we assume that unsigned is a 32bit integer type void srand1(unsigned S){ X = S; } unsigned nextInteger1(void){ X = X * 1103515245 + 12345; return (X / 65536) % 32768; } void generator1(int N, unsigned S, int A[]){ srand1(S); for(int i=1;i

The 2nd generator works as follows (C++ code):

/* ------------------ start here ---------------------*/ unsigned x, y, z, w; // we assume that unsigned is a 32bit integer type void srand2(unsigned S){ x = S; y = x * S; z = y * S; w = z * S; } unsigned nextInteger2(void){ unsigned t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } void generator2(int N, unsigned S, int A[]){ srand2(S); for(int i=1;i

Note that the LCG used in the 1st generator is the same one suggested in ISO/IEC 9899 (pp. 346--347), and Xorshift used in the 2nd generator is the same one in the paper by Marsaglia (July 2003).

Input

The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.

Each test case has only one line. The line contains the string of length N, denoting the array A[1], A[2], ..., A[N], where the string consists of only characters '0' and '1', and the i^th character denotes A[i].

Note that the integer N is not given in the input explicitly.

Output

For each test case, print "LCG" if the given sequence generated by the 1st generator, or print "Xorshift" if the given sequence is generated by the 2nd generator.

Constraints and Subtasks

• 1 = T = 30
• There is no pair of integers (s, t) such that 0 = s, t = 10⁹ and both generator1(N, s, A) and generator2(N, t, A) generate the given sequence. (Thus the answer will be determined uniquely)

Subtask 1 (10 points)

• 50 = N = 500
• There is an integer 0 = s = 500 such that generator1(N, s, A) or generator2(N, s, A) generates the given sequence.

Subtask 2 (40 points)

• 500 = N = 100000
• There is an integer 0 = s = 31313 such that generator1(N, s, A) or generator2(N, s, A) generates the given sequence.

Subtask 3 (20 points)

• 100000 = N = 200000
• There is an integer 0 = s = 10⁹ such that generator1(N, s, A) or generator2(N, s, A) generates the given sequence.

Subtask 4 (30 points)

• 500 = N = 200000
• There is an integer 0 = s = 10⁹ such that generator1(N, s, A) or generator2(N, s, A) generates the given sequence.

Example

Input: 6 1101100100101111010011010101110100001000000101001110101011010101010 000101101110101101110110010111000000011001101110101 11010100010110001101010110111000010001110010010011011110010010110000001100110 01011010100111100111101001010010100100111000111110 0000000000000000000000001001001010101011001111101101010 11101001010000000111101001111111000010000111010011111000001111 Output: LCG LCG LCG Xorshift Xorshift Xorshift

Explanation

Example 1. generator1(67, 5, A) generates the given sequence.

Example 2. generator1(51, 8, A) generates the given sequence.

Example 3. generator1(77, 58, A) generates the given sequence.

Example 4. generator2(50, 5, A) generates the given sequence.

Example 5. generator2(55, 8, A) generates the given sequence.

Example 6. generator2(62, 58, A) generates the given sequence.

Notes for C++

At first, in the codes, almost every operation will be done with unsigned.
Thus operations will return the result modulo 2³².
For example,

X * 1103515245 + 12345

means that

(X × 1103515245 + 12345) mod 2³²,

and

(X / 65536) % 32768

means that

(floor(X / 65536) mod 32768) mod 2³²,

in terms of mathematical notations.

Then there are some bit operations in the 2nd generator.
The operators and >> denote bit shifts.
For example,

X

means that

(X × 2¹⁵) mod 2³²,

and

X >> 13

means that

floor(X / 2¹³).

And the operator ^ denotes bitwise XOR.