All Tracks Math Problem

Boring Game



Day 3 of the Test match has just ended, and it seems to be headed for a boring Draw.

Virat and Alastair were very bored and tired of fielding for full days on the ground. They met after the stumps for having a drink. While having the drink, they heard about a new game which they found more interesting than the match that was going on.

So, they decided to play this game on the 4th day, taking a break from the boring game which was going on. Since this game involves each person from the crowd and makes use of the useless 500/1000 rupee notes, everyone agreed to play the game, which is defined as follows :

  1. There are 'n' people in the crowd.
  2. ith person has ai number of notes. (1<=i<=n)
  3. In one move, the player (Virat or Alastair) selects one person, who has more than 1 notes, from the crowd, and takes 'x' number of notes from him, where x divides ai.
  4. The player cannot take all the notes from the person.
  5. Virat plays the first move, after which the two players alternate their turns.
  6. Both the players play optimally.
  7. The player who plays the last move wins the game.

Virat is desperate for a win, but he doesn't have enough time to plan a strategy as he has to give time to his girlfriend. So, he turns to you for help. He gives you the number of people in the crowd, and the number of notes each person is having, and asks you to tell him who will win the game.

Can you help him?

Input :

First line tells the number of test cases, t, then description of the t test cases follow.
The first line of each test case is 'n', the number of people in the crowd.
The next line contains n space separated integers, ai, the number of notes each person has.

Output :

Print "Virat" if Virat wins the game, otherwise, print "Alastair". (without quotes)

Constraints :

1 <= t <= 10
1 <= n <= 1000000
1 <= ai <= 1000000
Sum of n over all the test cases <= 1000000

Problem Setter: Sahil Prakash

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications