The Bread Bucket Challenge MIT Hostel is very famous for its Buttered toast it provides, during Sundays.

Navkrish loves the bread and wants to eat a lot of it, thus breaking the previous record(50 slices). So, he woke up early and prepared himself for the ordeal. But he was shocked to see most of his friends still sleeping. He always loves to eat along with k people, as k is his lucky number. So, he wants to wake his friends up. However, since it is a Sunday, Navkrish is afraid to wake anyone up.

He found that some of his friends are awake. So he asks them to wake someone else up, but he has to pay his friend for the risk that they are about to take.

The cost of ith person waking up the jth person is given in the danger matrix. He wants to spend the minimum amount. Also, the wake string follows. If wake[i]='Y', it means that the ith friend is awake. If it is 'N',it means that he is asleep.

Help him find the total money he has to shell out, to go eat. If it is impossible for Navkrish to wake k friends up, print "Poor Navkrish."(without quotes).

Input format The first line contains t, the number of test cases. The next line contains n, the number of friends. The next n lines contain the danger array. In the danger array, the cost is from '0'-'9' represents the cost values of 0-9, and A-Z represents the cost values of 10-35. The next line contains the integer, k.

Output Print t lines, each containing the answer.

Constraints

1<=ite<=100, the number of test cases 1<=N<=16