HumptyDumpty and the Game

All submissions for this problem are available.
Problem Statement
Humpty and Dumpty are very close friends. Humpty has recently performed exceptionally well in the End semester exams, so he has gained a lot of confidence. He challenges Dumpty for a Nim game. But Dumpty, as we all know, completely outwitting him, challenges him for a unique game of its own kind. Humpty settles after the argument that they will use following function somewhere in the game.
def check( x, y, k): if y> x: return 0 p = k while x>0 and y>0: if (y%k) > (x%k): return 0 x = x/p y = y/p return 1
Here % is the modulus operator.
The Game is as follows:
N positive integers are given, let them be represented by A[1] to A[N]. Before the first turn, players decide a positive integer k (k>1). The two players take turns. Now, in each turn the player should choose one positive integer x among the given N integers, and he can reduce the integer by an amount y (y is also a positive integer) if check( x, y, k) returns TRUE. The game ends when no move can be made. And obviously the player who makes the last move wins.
Can you find who will win the game, if both players play optimally, given the N integer numbers and an integer k, considering that Humpty always takes the first move.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains space separated integer values N and k. Second line of each test case consists of N space separated integers.
Output
Output T lines, each representing the winner. Output 1 if Humpty wins and 2 if Dumpty wins.
Constraints
1 ≤ T ≤ 10^{5}
1 ≤ N ≤ 10^{5}
2 ≤ k ≤ 10^{5}
1 ≤ A[i] ≤ 10^{18} for 1 ≤ i ≤ N
Example
Input: 2 3 4 5 6 9 3 3 1 5 2 Output: 1 2
Author:  savy1 
Tags  savy1 
Date Added:  27022015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 