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
haiderbaig: 2019-09-04 17:59:57

seemed impossible at first glance but then i took out a paper and a pencil and doodled a little.
DP is all about reducing a problem to sub-problems

ankityadav: 2019-07-01 06:58:30

just take care of cases when ada won and ada lose
2-d dp is enough
and take care of even odd turns

shehar48: 2019-05-19 21:18:42

Can anyone please point on the mistake in my code. I am getting WA. I have used 2D DP.
Here is the link to my code -

senseichrollon: 2019-04-10 00:17:12

Can someone give me a hint on approaching this? For example, is it better to solve this top-down, or bottom up?

Last edit: 2019-04-10 00:23:49
clarkfric_200: 2019-03-06 22:28:54

DP problems are so simple , yet so beautiful .

zurister: 2018-10-02 13:19:10

@morass can you provide me a testcase where my solution 22427308 fails?

code_aim: 2018-06-04 21:43:01

Can anyone provide me a test case as my code is failing at test case 8?

magicarp: 2018-05-29 18:40:19

@morass I hope you are doing great. I think there are test cases with N > 9999 or M > 100. When I check for them in my submission, it gives me WA. When I don't, it gives me RE. Please check. Thank you.

EDIT: Please Discard

Last edit: 2018-05-29 18:54:13
sinersnvrsleep: 2018-03-24 15:54:40

hi morass nice question getting constantly wrong answer on test case 7 i think my logic is correct plz help

manya_cod4: 2017-12-08 10:37:57

when i am submitting, after 8 testcase, Runtime exception is getting thrown. When i am running locally, no test case i am able to find that is throwing RE. I am running in java. Any suggestions @morass?

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