Digo is too much fond of marble gems.One day he sees n boxes arranged in a straight line each filled with infinite number of marble gems of k different color.He starts from first box and keeps moving forward by eating one gem at a time.If he eats the same color marble from two adjacent boxes then he may get infected with a severe syndrome known as digodrome .Given a marble has 'c' calories find out if digo tries every possible permutation of eating marbles without getting infected,how many calories can he gain.
Digo knows one thing that if a modulo m is b and c modulo m is d so a*c modulo m is b*d modulo m.Well,he isn't sure how to use it so he needs your help.
The first line contains the number of test cases t followed by t lines each containing three integers n,k,c and m where n is the number of boxes from which digo will have his gems, k is the number of marble colors each box has, c is the calorie gained by eating each marble and m is modulo for answer.
The output should have t lines each containing the amount of calories digo can have in this process. The answer should be %m of the calculated answer.
Explaination for test case 1:
He has two boxes and each box has 2 color marbles say red and blue.So he can have one red from first box and blue from second and then start again with one blue marble from first box and then red one from second.So he can have a total of 4 marbles without getting infected.As each marble is of 2 calories so the total calories are 8.