Akash is good at mathematics and games. He also has a nature of boasting about it. He invites his best friend to dinner and ask him to play his newly invented game.
He presents N numbers and an integer K. The game goes like this:
Each player will be given turn one by one. In each of their turn they can choose any number (non-zero) from the given array and divide (Integer division) it with K. The player who is unable to complete his move looses. Akash is very confident about his skills and knowledge about the game so he gives the first chance to his friends.
 
Example 1:
Input: nums = [1, 2, 3], k = 2
Output: Akash
Explanation: Friend will choose 2, then numbers
will become [1, 1, 3]. Akash will choose 3, 
then numbers will become [1, 1, 1].Friend will 
choose 1 then numbers become [0, 1, 1]. Akash 
will choose 1 then numbers will become 
[0, 0, 1]. Friend will choose 1 then numbers 
will become [0, 0, 0]. Now akash can't make 
a move.
Example 2:
Input: nums = [2, 4, 6], k = 2
Output: Friend
Explanation: Akash will win the game.
 
Your Task:
You don't have to read or print anything. Your task is to complete the function Play() which takes the list of numbers as input parameter and returns "Akash" if his friend wins otherwise returns "Friend" (Without quotes).
 
Expected Time Complexity: O(n * c) where c is constant.
Expected Space Complexity: O(1)
 
Constraints:
1 <= n <= 100000
2 <= k <= 1000000
1 <= numbers <= 1000000

Source: geeksforgeeks | Difficulty: EASY
Tags: Number theory

Starter code: #User function Template for python3

class Solution:
	def Play(self, nums, k):
		# Code here

Solutions:
class Solution:

	def Play(self, nums, k):
		x = 0
		for i in nums:
			g = i
			while g > 0:
				x += 1
				g = g // k
		if x % 2 == 1:
			return 'Akash'
		return 'Friend'


import math

class Solution:

	def Play(self, nums, k):
		s = 0
		for i in range(len(nums)):
			s += int(math.log(nums[i], k)) + 1
		if s & 1 != 0:
			return 'Akash'
		else:
			return 'Friend'


class Solution:

	def Play(self, nums, k):
		x = 0
		for i in nums:
			while i > 0:
				x += 1
				i = i // k
		if x & 1 == 1:
			return 'Akash'
		else:
			return 'Friend'
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		nums = list(map(int, input().split()))
		ob = Solution()
		ans = ob.Play(nums, k)
		print(ans)