Problem Statement:

“Silk” is the superstar of tamil cinema today.Many leading producers have approached her with huge salaries.The director of her first film pattupoochi wants a make a new film.Pattupoochi is not confident about his direction skills but he is confident about Silk's magic.So, he wants to book her for a song in this new movie.But silk's dates are already full for an year and pattupoochi cant wait an year for a song.So, he plans something clever.

Pattupoochi knows something about silk which nobody else knows.She is crazy about certain numbers called “Gilma numbers”.If pattupoochi can approach her with a salary that is a gilma number silk will surely accept his offer regardless of her dates.But pattupoochi is weak in mathematics and cant find which numbers are gilma numbers.

You are working as a technician in the new movie and pattupoochi approaches you to help him.He asks you to write a program that will say whether a number is a Gilma number or not.It is upto you to help pattupoochi or else you wont get your salary!!

Notes:

Lets define what's a Gilma number:

Any number 'N' is called a Gilma number if it can be expressed as a sum of a “Matter progression” of exactly 'K' terms.

A matter progression is a special arithmetic progression in which the first term 'a' and common difference 'd' are strictly postive integers.

Input Specification:

The first line of input contains an integer 'T' denoting the number of test cases.This is followed by 'T' lines.Each line contains two integers 'N' and 'K'.

Output Specification:

The output contains 'T' lines.

If the number 'N' is a gilma number,then print “Padam tharumaru machi!”

else print “Padam sotha machi!”

Constraints:

1<=T<=100

1<=N<=1000000

1<=K<=50

Input:

2                                                                                                  

1 2

12 3

Output:

Padam sotha machi!

Padam tharumaru machi!

Test case explanantion:

'1' cannot be expressed as sum of matter progression containing 2 terms.

'12' = 1+4+7

which is a matter progression containing 3 terms.