ADAGAME4  Ada and Game of Divisors
Ada the Ladybug is playing Game of Divisors against her friend Velvet Mite Vinit. The game has following rules. There is a pile of N stones between them. The player who's on move can pick at least 1 an at most σ(N) stones (where σ(N) stands for number of divisors of N). Obviously, N changes after each move. The one who won't get any stones (N == 0) loses.
As Ada the Ladybug is a lady, so she moves first. Can you decide who will be the winner? Assume that both players play optimally.
Input
The first line of input will contain 1 ≤ T ≤ 10^{5}, the number of testcases.
The next T lines will contain 1 ≤ N ≤ 2*10^{7}, the number of stones which are initially in pile.
Output
Output the name of winner, so either "Ada" or "Vinit".
Example Input
8 1 3 5 6 11 1000001 1000000 29
Example Output
Ada Vinit Ada Ada Vinit Vinit Ada Ada
hide comments
dictator97:
20171218 17:27:25
how 29 gives vidit i dont get it can someone please help 

manya_cod4:
20171216 06:05:28
@morass. Thanks. i was able to find the divisors in the much more efficient.


manya_cod4:
20171215 14:17:59
Can someone provide with some good testCases? Thanks in advance.


morass:
20171215 08:42:50
@manya_cod4: Good day to you. Imho it shall require better complexity. Even though some solutions might be slower, it could be done in linear time.


manya_cod4:
20171215 07:57:15
Beside using DP, my algorithm need to find number of divisors for every number in the range 2 * 10000000 + 1, which takes sqrt(n) for each n. Therefore O(n) comes out to be O(n * sqrt(n)) which is giving me TLE. Can anybody confirm if this solution needs complexity lesser than that?


morass:
20171214 02:36:17
@barishnamazov: positive 

barishnamazov:
20171213 18:30:47
Is sigma(N) is count of *all* divisors of N or count of *positive* divisors of N? 
Added by:  Morass 
Date:  20171208 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 