8639: Ironforge

The subway of Ironforge can been seen as a chain of $n\ge 2$ vertices. In other words, for each $i=1,2,\mathrm{3...}n-1$, there is an edge between vertex $i$ and vertex i+1

There is a number ai(1≤i≤n) on vertex $i$ and a prime number bi(1≤i<n) written on the edge between vertex i and vertex $1$.

You may start a trip on some vertex with an empty bag. When you are on vertex i, you can put all prime factors of ai into your bag. You can walk through an edge with prime number p written on it if and only if you already have p in your bag. You are allowed to pass each vertex and each edge multiple times.

You need to answer $m$ queries. In each query you are given two numbers x,y. You need to answer whether you can reach vertex y if you start your trip on vertex $x$ by the subway of Ironforge.

The input consists of multiple test cases.

The first line contains an integer $T(1\le T\le 3)$ denoting the number of test cases.

For each test case, the first line contains two integers n and m (2≤n,m≤2×105), denoting the number of vertices and the number of queries.

The second line contains n integers ai (1≤i≤n,1≤ai≤2×105).

The third line contains n-1 integers bi (1≤i<n,2≤bi≤2×105).

Following m lines describe the queries. Each line contains two integers $x,y(1\le x,y\le n)$.