Killjee and Saraff lives in Codaland there are n cities in Codaland, Every city is connected to all other city by undirected roads such that, only an unique path exist between any pair of cities. Saraff and killjee are planning to meet someday they can meet in any city which lies in the path from Saraff's home city to killjee's home city and its city id is prime number.

Now, killjee wonders how many cities are eligible to become their meeting place. As, Saraff is busy in selecting a gift for killjee and killjee is a super noob in programming please help them.

You will be given q queries each query will contain Saraff's home city and Killjee's home city.

CONSTRAINTS

\(1 \le n \le 2*10^5\)

\(1 \le u,v \le n\)

\(1 \le q \le 10^6\)

\( 1\le \) Saraff's Home city,Killjee's Home city \(\le n\)

INPUT

First line of input contains a single integer n. \(n-1\) lines follow each containing two space separated integers u and v, denoting a road between u and v.

Next line contain a singe integer contain a single integer q denoting number of queries. q line follows each containing two space separated integers denoting Saraff's Home city and Killjee's Homee city respectively.

OUTPUT

Print a single integer for each query, denoting number of eligible cities.