D. Producing Digits
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For each test case, you are given arrays $$$a$$$ and $$$b$$$ with $$$n$$$ integers. For each $$$a_i$$$ determine whether you can multiply $$$a_i$$$ by any subset of the previous elements in the array (subset may be empty, meaning you do not multiply) such that the ones (unit) digit of the product is the digit $$$b_i$$$.

When working with negative numbers, the units digit still refers to the last digit when writing down the number. (The units digit of $$$-19$$$ is $$$9$$$)

Input

The first line gives the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The first line of each test case gives $$$n$$$, the size of the array ($$$1 \le n \le 10^5$$$). The sum of all $$$n$$$ is less than $$$n \le 5 \cdot 10^5$$$. The second line of each test case gives $$$n$$$ integers, $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$). The third line of each test case gives $$$n$$$ integers, $$$b_i$$$ ($$$0 \le b_i \le 9$$$).

Output

For each test case, print a string of length $$$n$$$ consisting of $$$N$$$s and $$$Y$$$s. For each element $$$a_i$$$, on the $$$i$$$-th character use a $$$Y$$$ if it is possible to create a product with the correct units digit or an $$$N$$$ if it is not possible.

Example
Input
2
5
1 2 3 4 5
2 2 2 3 4
10
3 3 3 -3 3 3 3 -3 -3 3
1 1 1 1 2 3 4 5 6 7
Output
NYNNN
NNNYNYNNNY