ADAGAME - Ada and Game

Ada the Ladybug is playing Game of Digits against her friend Velvet Mite Vinit. The game is played in following manner: At first, there is a four-digit number and a number of moves. Both Ada and Vinit take turns alternately (beginning with Ada). Both of them must increase ANY digit of the number, but if the digit was 9 it will become 0.

For example number 3590 can be expanded to: 4590, 3690, 3500 or 3591. If after all turns the number is greater than the original number, Ada wins - otherwise Vinit is the winner. Both of them play optimally - can you decide who is the winner?

PS: It is possible, that Ada will have one more turn (if number of turns is odd)

Input

First line of input will consist T ≤ 200 number of test-cases. Each testcase will consist of four digit number 0 ≤ N < 104 [the original number] and 0 ≤ M ≤ 100 [the number of turns].

Output

For each test-case, print the name of winner ("Ada" or "Vinit").

Example Input

5
0000 0
5566 3
3333 10
9999 9
1234 30

Example Output

Vinit
Ada
Ada
Vinit
Ada

Added by:Morass
Date:2016-09-06
Time limit:4.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2016-12-10 12:59:39
@kira28: You mean after one turn? 9590 (if aplied to first digit first digit)
2016-12-10 11:36:29
question is not clear
1
8590 5
after all turn this would be 9590 or 0590?
2016-12-06 19:41:59
@pandey333: Good day to you - sure, for example:

1
7862 32
2016-12-06 17:29:23
@morass
can you please give me a test case where "vinit" wins ,except(str[]='9999' or m=0).?
2016-09-28 14:38:18
@Bhuvnesh Jain: Good day to you, sure "7820 85" shall be "Ada" but your output says "Vinit" :)
2016-09-28 14:17:53 Bhuvnesh Jain
@morass, could you please give a test case where my submission number 17804732 fails the expected solution. It would be very nice of you.

Edit: Done in 0.99 sec. Can you give hint of how to optimise it further? Or it is just that recursive, as in all cases, will be slower than iterative version.

Last edit: 2016-10-09 10:27:32
2016-09-15 01:58:28
@ashwin9686: Good day to you. Here's a test-cases:

1
8261 2

Your program outputs "Vinit", anyway "Ada" will win (Ada picks any number other than the first and Vinit has no way to win then)!
2016-09-14 21:44:52
@morass I can't seem to figure out any corner cases where my answer seems wrong. Either the logic of my problem is wrong or the test case (8) is not fine. I please ask you to figure out a problem in either of them. Thank you.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.