Giải bài trực tuyến

Multiplicative functions are defined as functions such that f(m*n) = f(m) * f(n). Now, we put an extra constraint on multiplicative functions that if m and n are coprime , then f(m) and f(n) are also coprime. Additionally it is also provided that f(1)=1. f(x) is defined for positive integers and it returns positive integers.

Now, you are provided with some x and corresponding f(x). Your task is to find out , if you can uniquely determine the value of f(y) given y and if yes, find the value.

Input

The first line of input contains a number representing the number of test cases. For each test case, the first line contains a number N representing the number of (x,f(x)) pairs to be provided. N Lines follow, each line containing a pair of space separated numbers : the first one corresponding to x and second one to f(x). Next line contains q, the number of queries. q lines follow, each containing a number y.

Output

For each test case output q lines, one corresponding to each query. The output should contain "YES f(y)" where f(y) is replaced by the integer denoting f(y) with no leading zeroes if given the data, we can uniquely determine f(y), or "NO" if the input data is inconsistent with the properties of the function or with the given information provided about the function, we can not uniquely determine f(y).

Example

Input:
3
3
2 2
3 2
7 19
1
7
1
6 6
1
6
2
2 2
3 3
1
12

Output:
NO
YES 6
YES 12

Constraints

Dataset 1: The number of test cases are less than 20. N ≤=50. x and f(x) ≤ 10^50 . x and f(x) do not have a prime factor greater than 100005.

The number of queries are less than or equal to 50. Each number in the query is less than 10^50. You are guaranteed that if the answer is unique, it contains less than 400 digits. Time limit: 12s