Time Limit: 1.5 s

Memory Limit: 256.0 MB

Description

Once upon a time in a charming town, there lived a young man named Roy, a computer science student passionate about solving problems. He had a crush on a vibrant girl named Setia, whose smile could brighten any day. As he navigated his feelings for her, he faced a challenge with an array \(A[]\) of \(N\) elements and a positive integer \(X\).

For \(Q\) queries, he needed to determine if there was a subarray between indices \(L\) and \(R\)(inclusive) whose product was divisible by \(X\). While pondering this, Roy mustered the courage to ask Setia out. To his delight, she agreed to coffee that weekend.

Their date was magical, filled with laughter and deep conversations. As they strolled through the park under twinkling stars, Roy felt a connection that surpassed any algorithm. He realized that love, like coding, required patience and courage.

Now, as he worked on his problem, he saw the beauty in both math and matters of the heart. Roy knew that solving challenges and exploring a budding romance with Setia were journeys worth embracing together.

Suppose, You have an array \(A[]\)={\(5, 2 , 4\)}.
All possible subarray product of this array \(A[]\) is,
from (\(1\) to \(1\)) = \(5\),
from (\(2\) to \(2\)) = \(2\),
from (\(3\) to \(3\)) = \(4\),
from (\(1\) to \(2\)) = \(5 * 2\) = \(10\),
from (\(2\) to \(3\)) = \(2 * 4\) = \(8\),
from (\(1\) to \(3\)) = \(5 * 2 * 4\) = \(40\).

Input

First lint \(T\), the number of test case.
In each test case, first line two positive integers \(N\) and \(X\).
Second line, an array \(A[]\) with exactly \(N\) elements.
Third line \(Q\), the number of queries.
Fourth line, in each query two positive integers \(L\) and \(R\).

\(1<=T<=10^3\)
\(1<=N,Q<=10^5\)
\(1<=A[]<=10^9\)
\(1<=X<=10^9\)
\(1<=L<=R<=N\)
Sum of N and Q overall test case doesn't exceed \(2 * 10^5\)

Output

In each query print Yes, if exist a subarray within ranges, which product is divisble by \(X\), otherwise print No.

Sample

1
5 4
2 6 2 7 8
3
3 4
2 3
5 5

No
Yes
Yes

First test case :
First query (\(L=3\) to \(R=4\)) :
all possible subarray product given range,
from( 3 to 3) =2,
from( 4 to 4) =7,
from( 3 to 4) = 2 * 7 = 14,
Theres is no subarray product which is divisble by \(X=4\).

Second query (\(L=2\) to \(R=3\)) :
all possible subarray product given range,
from( 2 to 2) =6,
from( 3 to 3) =2,
from( 2 to 3) = 6 * 2 = 12, is divisble by \(X=4\).