Pass the Ball
Time Limit: 3 sec
The Problem
Pass the ball is an interesting game for me. I always play this game when I go to my beloved village. Now I will explain this for you. In this game there are N people stands in a field. Here person P has to send a ball to the person Q directly or by passing the balls to others. To play this game at first the judge of this game will give a card with a PASS number to everyone which is the most important number for this game. A person can pass the ball to another person if and only if the PASS number of the two persons has a common divisor greater than 1. Suppose 15 and 21 has a divisor 3, 4 and 8 has a common divisor 2, so 4 and 8 can pass the balls to each other. In case of 4 and 15 4 can’t pass the balls to the 15, because 4 and 15 don’t have a divisor greater than 1. Then the judge will randomly select person P and person Q and gives the ball in hand of person P and give order to send the ball to the person Q. If person P can’t send this ball to the destination person, then P will be eliminated from this game. In this way the game will continue until the 2nd last person will eliminated.
Now you are thinking what you have to do in this game. Am I right?? …….
Here you noticed that to send the ball from person P to person Q some people will get the ball to pass forward. There can be more than one way to send the ball. Now you have to print a number S.
S = {the minimum number of person who pass the ball (including P and Q)} – 1
The Input
The input starts with a number T (0<T<21) , the number of test cases. Every test case starts with a line contain a single positive integer N (1<N<101), the number person will play this game. The second line will contain N space separated integer PASSi < 1000. Third line will contain a single integer M (0<M<501), the number of query the judge will play. The next M lines will contain two space separated integers P and Q (1<=P, Q<=N).
The Output
For each query of the input if it is possible to send the ball from P to Q then print the integer S described in above otherwise, print “Impossible”.
Sample Input
1
8
22 45 8 2 76 12 39 83
4
1 8
4 7
8 3
2 4
Sample Output
Impossible
2
Impossible
2
[Outsbook Round #1 Online Contest]
Problem Setter: Milton Deb