Gru wanted to upgrade the quality of his minions' despicableness through his new base, The Volcano. Dave, desperately wanting the Minion of the Year award, rushed to The Volcano only to find out that he needs to solve a series of questions before he can unlock the gate and enter.

Dave is given a prime , and questions.

In each question/query, Dave is given four integers , and Dave needs to find the minimum possible value of among all positive integer pairs such that divides .

Unfortunately, the gate has a strict time limit, and if Dave is unable to answer all questions quickly and correctly, then a hidden freeze ray will zap him and he won't be able to move. Please help Dave answer all the questions so he can enter The Volcano and win the Minion of the Year award!

Input Format
The first line of input consists of an integer, , which is the number of test cases.

The first line of each test case consists of two integers separated by a space, and . The following lines contain the queries, each in a line. Each question consists of four integers separated by single spaces: , , and .

Output Format
For each query, output a single line containing the minimum value of , or output wala if no such pairs exist.

Constraints




is prime

Sample Input

2
7 2
1 1 1 5
7 8 8 7
11 5
1 1 1 1
0 1 2 3
3 2 1 0
9 8 7 6
0 0 1 1

Sample Output

7
wala
2
1
wala
33
0

Explanation
For the first query, , , the minimum is , which occurs at ( divides ).

For the second query, no matter what you choose, will not by divisible by , so the answer is wala.