You have been given a graph consisting of ‘N’ nodes and a threshold value ‘THRESHOLDVALUE’. Two different nodes ‘X’ and ‘Y’ are directly connected to each other if and only if there exists a ‘Z’ such that all of the following are true:-

‘X’ % ‘Z’ == 0 
‘Y’ % ‘Z’ == 0
‘Z’ >= ‘THRESHOLDVALUE’

You are given ‘Q’ queries where each query consists of two distinct nodes ‘U’ and ‘V’, you must determine if ‘U’ and ‘V’ are connected directly or indirectly. Return a vector/list of size ‘Q’ where ‘i-th’ element is ‘1’ if nodes in ith query are connected directly or indirectly otherwise it is ‘0’.

Example:

Let’s say ‘N’ is 6 and 'M' is ‘2’. Then our graph will look as follows:-

There is an edge between ‘2’ and ‘4’, ‘4’ and ‘6’ and ‘2’ and ‘6’ because their gcd is 2 which is equal to ‘m’. There is an edge between ‘3’ and ‘6’ because their gcd is 3 which is greater than ‘m’. If the query consists of vertices ‘2’ and ‘3’ answer will be ‘1’ because they are indirectly connected.

Input Format:

The first line contains a single integer ‘t’ representing the number of test cases.

The first line of each test case contains two space-separated integers ‘n’ and ‘THRESHOLDVALUE’ representing the number of nodes and the threshold value.

The second line contains a single integer ‘q’ representing the number of queries.

Each of the next ‘q’ lines contains two space-separated integers representing the vertices for which you need to find if they are connected directly or indirectly.

Output Format:

For each test case, print a single line containing space-separated integers denoting answers to all the queries. 

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 10
1 <= N <= 100
1 <= THRESHOLDVALUE <= 100
1 <= Q <= 10000
1 <= U[i] <= N
1 <= V[i] <= N

Where ‘T’ is the number of test cases.‘N’ is the number of nodes in the graph. ‘THRESHOLDVALUE’ is the threshold value. ‘Q’ is the number of queries. ‘U[i]’ and ‘V[i]’ are vertices of the i-th query.

Time Limit: 1 sec.