ADAGAME4 - Ada and Game of Divisors

no tags 

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 and at most σ(N) stones (where σ(N) stands for the number of positive 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 ≤ 105, the number of test-cases.

The next T lines will contain 1 ≤ N ≤ 2*107, 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: 2017-12-18 17:27:25

how 29 gives vidit i dont get it can someone please help

manya_cod4: 2017-12-16 06:05:28

@morass. Thanks. i was able to find the divisors in the much more efficient.

manya_cod4: 2017-12-15 14:17:59

Can someone provide with some good testCases? Thanks in advance.

morass: 2017-12-15 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.

Good Luck & Have Nice Day!

manya_cod4: 2017-12-15 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: 2017-12-14 02:36:17

@barishnamazov: positive

barishnamazov: 2017-12-13 18:30:47

Is sigma(N) is count of *all* divisors of N or count of *positive* divisors of N?


Added by:Morass
Date:2017-12-08
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All