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 optimaly - can you decide who is the winner?

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


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].


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

Example Input

0000 0
5566 3
3333 10
9999 9
1234 30

Example Output


hide comments
piuspbd: 2017-03-27 00:37:54


sharma96: 2016-12-28 10:49:37

@morass , does this problem uses a known DP algorithm or it's just a logical question?

Last edit: 2016-12-28 19:20:33
morass: 2016-12-10 23:03:34

@kira28: That if there exists a move which leads to sure victory {if no mistake appear - and it won't appear} then the player will choose such move [i.e since none will make any mistake it is possible {for each state} to decide who will win]

kira28: 2016-12-10 17:27:58

@morass what does "both of them play optimally" stand for?

morass: 2016-12-10 15:45:29

@kira28: oh .. well hard to say... I can say that Vinit will win- there is nothing Ada can do about it ... an example of "how it can end" is by number "0593" - but since it doesn't matter for Ada what steps she will do, the result can be as well "3590"

kira28: 2016-12-10 14:36:03

@morass after all 5 turns.what will be that number which we will compare with the orignal number , to decide the winner

morass: 2016-12-10 12:59:39

@kira28: You mean after one turn? 9590 (if aplied to first digit first digit)

kira28: 2016-12-10 11:36:29

question is not clear
8590 5
after all turn this would be 9590 or 0590?

morass: 2016-12-06 19:41:59

@pandey333: Good day to you - sure, for example:

7862 32

pandey333: 2016-12-06 17:29:23

can you please give me a test case where "vinit" wins ,except(str[]='9999' or m=0).?

Added by:morass
Time limit:4.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU