Mojan kibutsuji is an evil demon who eats people and can turn people into demon. Tanjiro is a swordsman whose family is slaughtered by Mojan. Tanjiro wants to kill mojan but, in order to do that he needs to master the sun breathing technique. There is a secret library that contains a book about sun breathing technique. After searching for 5 months tanjiro finally found the library. But tanjiro shocked when he entered into the library.There were millions of books and tanjiro doesn’t know the serial number of the book he is looking for. Tanjiro found a sequence written in the wall of the library which will give him the serial number of the book. As tanjiro is super bad at math he wants your help to solve the following sequence.
Input
The input begins with the number of cases T (1 ≤ T ≤ 10,0000). In each of the following T lines you will find four non negative integers: A, n, k, m. Here k is a power of 2().
1 <= A <= 10^6
1 <= m <= 1000
1 <= k <= 20
1 <= n <= 10^6
Output
For each case, output the value of the sequence S.
Sample
| Input | Output |
|---|---|
1 5 2 2 1 | 8 |
