#!/usr/bin/env python

# Time Travel
# Phil Bordelon

import os
import sys

DEBUG = os.getenv("DEBUG", False)


# Are you surprised to find a class doubling as a struct here?  I hope not.
class Struct():

# bellmanFord ... uh ... yeah.  While predecessor edges aren't used,
# we track them so that we can print a nice debug path.
def bellmanFord(vertex_list, edge_list, start, finish):

   # A set of vertex objects, initialized to an infinite distance away.
   real_vertices = {}
   for vertex in vertex_list:
      real_vertex = Struct()
      real_vertex.year = vertex
      if vertex == start:
         real_vertex.distance = 0
         real_vertex.distance = LATEST_YEAR + 1
      real_vertex.predecessor = None

      real_vertices[vertex] = real_vertex

   for i in range(len(vertex_list) - 1):
      for edge in edge_list:
         one_end = real_vertices[edge[0]]
         other_end = real_vertices[edge[1]]
         if other_end.distance > one_end.distance + edge[2]:
            other_end.distance = one_end.distance + edge[2]
            other_end.predecessor = one_end

   if DEBUG:
      to_print = ""
      curr_vertex = real_vertices[finish]
      while curr_vertex.predecessor:
         to_print += "%d (%d) <-- " % (curr_vertex.year, curr_vertex.distance)
         curr_vertex = curr_vertex.predecessor
      to_print += "%d" % (start)
   return real_vertices[finish].distance

# travelThroughTime simulates time travel, considerably less interestingly
# than I suspect the real thing would be.
def travelThroughTime(universe, goal_year):

   # Time travel takes place in two phases: start year to goal year, then
   # goal year back to start year.  We're going to use copies of the universe
   # vertex/edge data so as not to clutter it up with unnecessary edges, plus
   # the relaxation process will obviously muck with the structures anyways.
   vertex_list = universe.vertex_list[:]
   edge_list = universe.edge_list[:]

   # If the goal year isn't already an entry in the vertex list, make it so.
   if goal_year not in vertex_list:

   # Sort the vertex list ...

   # And now we add the slow, boring, 1-year-per-year travels of Real Time(tm)
   # to the edge list, basically adding an edge between each subsequent year
   # of the difference between those years.  We only care about 'key' years,
   # such as ones with wormholes or start/ends, so this works nicely.
   for i in range(len(vertex_list) - 1):
      edge_list.append((vertex_list[i], vertex_list[i + 1],
       vertex_list[i + 1] - vertex_list[i]))

   # Now we actually run Bellman-Ford across this puppy.  B-F will make its
   # own fresh copies of the lists to not mess with stuff, and return the
   # distance.  How very nice of it!
   there = bellmanFord(vertex_list, edge_list, universe.start_year, goal_year)
   back = bellmanFord(vertex_list, edge_list, goal_year, universe.start_year)

   return(there + back)

def main():

   dataset_count = int(sys.stdin.readline())
   for dataset_loop in range(dataset_count):

      print("DATA SET #%d" % (dataset_loop + 1))

      universe = Struct()

      # Get the number of wormholes in this universe.
      universe.wormhole_count = int(sys.stdin.readline())
      universe.edge_list = []
      universe.vertex_list = []

      # Read in each wormhole, adding them as edges.  We also track the
      # furthest in the future a wormhole can be entered, and the furthest
      # in the past one can be exited, as no missions beyond those years
      # can be handled, and all missions in between those can.

      latest_entrance = EARLIEST_YEAR - 1
      earliest_exit = LATEST_YEAR + 1
      for i in range(universe.wormhole_count):

         entrance, exit = [int(x) for x in

         if DEBUG:
            print("Wormhole from %d to %d found." % (entrance, exit))

         # Add the entrance and exit to the vertex list.
         for j in entrance, exit:
            if j not in universe.vertex_list:

         if entrance < exit:

            # Forward wormhole.  Halve the time passed.
            edge_weight = (exit - entrance) / 2
            universe.edge_list.append((entrance, exit, edge_weight))

            if DEBUG:
               print("   (It costs %d to traverse.)" % (edge_weight))

         elif exit < entrance:

            # Backwards wormole.  Negative quarter time.
            edge_weight = -((entrance - exit) / 4)
            universe.edge_list.append((entrance, exit, edge_weight))

            if DEBUG:
               print("   (It costs %d to traverse.)" % (edge_weight))

            # We don't care about NOP wormholes.

         # Update our latest entrances and earliest exits if appropriate.
         if latest_entrance < entrance:
            latest_entrance = entrance

         if earliest_exit > exit:
            earliest_exit = exit

      if DEBUG:
         print("Time travel can handle years %d through %d." % (earliest_exit, latest_entrance))

      # Get the start year.
      universe.start_year = int(sys.stdin.readline())
      if universe.start_year not in universe.vertex_list:

      # Now, let's handle the missions.
      mission_count = int(sys.stdin.readline())
      for mission_loop in range(mission_count):

         goal_year = int(sys.stdin.readline())

         # A mission is undoable only if either the start year is out of
         # the network of wormholes or the destination year is out of
         # the network of wormholes.  Don't even bother trying to compute
         # if those are the case ... except for when the goal year is the
         # same as the start year.  This is a trivial corner case.
         if (universe.start_year < earliest_exit or
          universe.start_year > latest_entrance or goal_year < earliest_exit or
          goal_year > latest_entrance):
            if universe.start_year != goal_year:

            # Time travel, baby!
            time_taken = travelThroughTime(universe, goal_year)

if "__main__" == __name__: