Juggler

All submissions for this problem are available.
You recently visited The Great Circus at Pilani. You saw a few jugglers at the circus and you really liked their performances. Being really good at math and analytical skills, you can't help but look at juggling from a mathematical perspective.
So what exactly is juggling? Before defining it, we will try to get a feel of what it is by looking at various examples.
What you see here are different 'patterns' of juggling.
Definition of juggling
Making a move with a hand: When a juggler makes a move with a hand, he checks if there is a ball in that hand. If there is a ball in that hand, he throws it (this is called a normal throw). Otherwise, he doesn't do anything with that hand (this is called an empty throw).
 A juggler cannot have more than one ball in a hand at any given time.
 A juggler makes a move alternately with his left and right hands (i.e. he cannot move with both his hands or make 2 consecutive moves with the same hand).
 The time interval between any 2 consecutive moves is constant. That constant is known as a tick.
Formalizing a juggling pattern
In juggling, there are many different ways of throwing a ball (you can notice that in the examples). Suppose a ball is thrown at time t_{1}. It is caught at rethrown at time t_{2}. Then t_{2}t_{1} divided by the duration of a tick is called the order of that throw. Order of an empty throw is 0.
We can characterize a juggling pattern by the order of its throws. For eg, in the first example all throws are of order 3. In the second example, throws of order 5 and 3 are alternating. Since juggling patterns are periodic, we write a few throw orders and assume that the throw orders keep repeating. This representation of a juggling pattern is called 'Throw Order Sequence' (TOS).
For the examples given above, these are the TOSes:
 [3]
 [5, 3]
 [5, 1]
 [4]
 [5]
 [4, 4, 1]
 [5, 0, 5, 0, 5]
 [5, 3, 4]
More specifically, let S be a TOS of length N. That means that the (i+1)^{th} throw has order S[i%N], where i is any nonnegative integer. The (i+1)^{th} throw happens at time i (counting in ticks). Further, if i is even, the (i+1)^{th} throw is made using the right hand. If i is odd, the (i+1)^{th} throw is made using the left hand.
A sequence of numbers may or may not be a TOS of any juggling pattern. You will be given a sequence of integers and you have to tell whether it is a valid TOS.
Input
The first line contains an integer T, the number of test cases.
The first line of each test case contains a single integer N, the number of elements in the sequence.
The next line contains N spacesepatated numbers, which is the sequence you have to analyze.
Output
For each of the T sequences, output (on separate lines) "Valid" if the sequence is valid and "Invalid" otherwise.
Constraints
1 ≤ T ≤ 10000
1 ≤ N ≤ 100000
The sum of N for all test cases does not exceed 10^{6}.
The numbers in the sequence range from 0 to 10^{9}. There will be at least one positive integer in the sequence.
Sample input
7
3
5 3 4
2
5 3
9
5 3 4 5 3 4 5 3 4
2
3 5
3
4 4 2
2
4 1
4
8 0 4 0
Sample Output
Valid
Valid
Valid
Valid
Invalid
Invalid
Valid
Explanation
The 3^{rd} TOS is equivalent to the 1^{st} TOS and the 4^{th} TOS is equivalent to the 2^{nd} one. This is because juggling is periodic. The first and the third TOS correspond to the throw orders ...53453453453...
and the 2^{nd} and 4^{th} TOSes correspond to throw orders ...535353535...
respectively.
Author:  sourabh13 
Tags  sourabh13 
Date Added:  26022016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, RUBY, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 