//note: too slow for kattis to accept

/**
 * Squares stuff
 */
let squaresLessOrEqualTo = function(n) {
    let count = Math.floor(Math.sqrt(n));
    let squares = [];
    for(let i = 1; i <= count; i++) {
        squares.push(i * i);
    }
    return squares;
};

let squareSums = function(n) {
    let allSquares = squaresLessOrEqualTo(n);
    let sums = [];
    //O(n^2), find faster way
    for(let i = 0; i < allSquares.length; i++) {
        for(let j = 0; j < allSquares.length; j++) {
            let a = allSquares[i];
            let b = allSquares[j];
            if(a + b === n) sums.push([a, b]);
        }
    }
    return sums;
};

/**
 * Graph stuff
 */
//pqueue from http://eloquentjavascript.net/1st_edition/appendix2.html
function BinaryHeap(scoreFunction){
  this.content = [];
  this.scoreFunction = scoreFunction;
}

BinaryHeap.prototype = {
  push: function(element) {
    // Add the new element to the end of the array.
    this.content.push(element);
    // Allow it to bubble up.
    this.bubbleUp(this.content.length - 1);
  },

  pop: function() {
    // Store the first element so we can return it later.
    var result = this.content[0];
    // Get the element at the end of the array.
    var end = this.content.pop();
    // If there are any elements left, put the end element at the
    // start, and let it sink down.
    if (this.content.length > 0) {
      this.content[0] = end;
      this.sinkDown(0);
    }
    return result;
  },

  remove: function(node) {
    var length = this.content.length;
    // To remove a value, we must search through the array to find
    // it.
    for (var i = 0; i < length; i++) {
      if (this.content[i] != node) continue;
      // When it is found, the process seen in 'pop' is repeated
      // to fill up the hole.
      var end = this.content.pop();
      // If the element we popped was the one we needed to remove,
      // we're done.
      if (i == length - 1) break;
      // Otherwise, we replace the removed element with the popped
      // one, and allow it to float up or sink down as appropriate.
      this.content[i] = end;
      this.bubbleUp(i);
      this.sinkDown(i);
      break;
    }
  },

  size: function() {
    return this.content.length;
  },

  bubbleUp: function(n) {
    // Fetch the element that has to be moved.
    var element = this.content[n], score = this.scoreFunction(element);
    // When at 0, an element can not go up any further.
    while (n > 0) {
      // Compute the parent element's index, and fetch it.
      var parentN = Math.floor((n + 1) / 2) - 1,
      parent = this.content[parentN];
      // If the parent has a lesser score, things are in order and we
      // are done.
      if (score >= this.scoreFunction(parent))
        break;

      // Otherwise, swap the parent with the current element and
      // continue.
      this.content[parentN] = element;
      this.content[n] = parent;
      n = parentN;
    }
  },

  sinkDown: function(n) {
    // Look up the target element and its score.
    var length = this.content.length,
    element = this.content[n],
    elemScore = this.scoreFunction(element);

    while(true) {
      // Compute the indices of the child elements.
      var child2N = (n + 1) * 2, child1N = child2N - 1;
      // This is used to store the new position of the element,
      // if any.
      var swap = null;
      // If the first child exists (is inside the array)...
      if (child1N < length) {
        // Look it up and compute its score.
        var child1 = this.content[child1N],
        child1Score = this.scoreFunction(child1);
        // If the score is less than our element's, we need to swap.
        if (child1Score < elemScore)
          swap = child1N;
      }
      // Do the same checks for the other child.
      if (child2N < length) {
        var child2 = this.content[child2N],
        child2Score = this.scoreFunction(child2);
        if (child2Score < (swap == null ? elemScore : child1Score))
          swap = child2N;
      }

      // No need to swap further, we are done.
      if (swap == null) break;

      // Otherwise, swap and continue.
      this.content[n] = this.content[swap];
      this.content[swap] = element;
      n = swap;
    }
  }
};

let createVertex = function(xPos, yPos, d) {
    return {
        xPos: xPos,
        yPos: yPos,
        d: d, //distance (in terms of number of coins) from origin
        edges: []
    };
}

let createEdge = function(v1, v2, w) {
    return {
        v1: v1,
        v2: v2,
        w: w
    };
}

//recursive function.
//used for creating graph only
let appendChildVertices = function(vertices, edges, parentVertex, coinTypes, eMod) {
    let newVertices = [];

    for(let i = 0; i < coinTypes.length; i++) {
        //check to see if new vertex won't go out of bounds
        let futureConvVal = parentVertex.xPos + coinTypes[i][0];
        let futureInfoVal = parentVertex.yPos + coinTypes[i][1];

        if(futureConvVal <= eMod && futureInfoVal <= eMod) {

            if(!vertices[futureConvVal]) {
                vertices[futureConvVal] = [];
            }

            let newEdge;
            if(vertices[futureConvVal][futureInfoVal]) {
                newEdge = createEdge(parentVertex, vertices[futureConvVal][futureInfoVal], 1);
                parentVertex.edges.push(newEdge);
                edges.push(newEdge);
            } else {
                let newVertex = createVertex(futureConvVal, futureInfoVal, 2000000000);
                newEdge = createEdge(parentVertex, newVertex, 1);

                parentVertex.edges.push(newEdge);
                edges.push(newEdge);
                vertices[futureConvVal][futureInfoVal] = newVertex;
                newVertices.push(newVertex);
            }
        }
    }

    for(let i = 0; i < newVertices.length; i++) {
        appendChildVertices(vertices, edges, newVertices[i], coinTypes, eMod);
    }
}

let createGraph = function(coinTypes, eMod) {
    //vertices are located by their x and y positions
    let vertices = [];
    let edges = [];

    //initial position
    let originVertex = createVertex(0, 0, 0);
    vertices[0] = [];
    vertices[0][0] = originVertex;
    appendChildVertices(vertices, edges, originVertex, coinTypes, eMod);

    return {
        vertices: vertices,
        edges: edges
    };
}

let dijkstra = function(graph) {
    let q = new BinaryHeap(function(a) {return a.d});

    //push vertices into pqueue
    for(let i = 0; i < graph.vertices.length; i++) {
        if(graph.vertices[i]) {
            for(let j = 0; j < graph.vertices[i].length; j++) {
                if(graph.vertices[i][j]) q.push(graph.vertices[i][j]);
            }
        }
    }

    while(q.size() !== 0) {
        let u = q.pop();

        for(let i = 0; i < u.edges.length; i++) {
            let edge = u.edges[i];
            let alt = u.d + edge.w;
            if(alt < edge.v2.d) {
                edge.v2.d = alt;
                q.remove(edge.v2);
                q.push(edge.v2);
            }
        }
    }
}

/**
 * Problem stuff
 */
let numProblems = parseInt(readline());
for(let i = 0; i < numProblems; i++) {
    let info = readline().split(' ');
    let numCoinTypes = parseInt(info[0]);
    let s = parseInt(info[1]);

    let coinTypes = [];
    for(let j = 0; j < numCoinTypes; j++) {
        let coinInfo = readline().split(' ');
        coinTypes.push([parseInt(coinInfo[0]), parseInt(coinInfo[1])]);
    }

    let graph = createGraph(coinTypes, s);

    let squareSumz = squareSums(s * s);
    let squareSumsExisting = [];
    for(let j = 0; j < squareSumz.length; j++) {
        let sqrt1 = Math.sqrt(squareSumz[j][0]);
        let sqrt2 = Math.sqrt(squareSumz[j][1]);

        if(graph.vertices[sqrt1]) {
            if(graph.vertices[sqrt1][sqrt2]) {
                squareSumsExisting.push([sqrt1, sqrt2]);
            }
        }
    }

    if(squareSumsExisting.length === 0) {
        print('not possible');
        if(i < numProblems - 1) readline();
        continue;
    }

    dijkstra(graph);

    let minCoins = 2000000000;
    for(let j = 0; j < squareSumsExisting.length; j++) {
        let index1 = squareSumsExisting[j][0];
        let index2 = squareSumsExisting[j][1];
        let d = graph.vertices[index1][index2].d;
        if(d < minCoins) minCoins = d;
    }

    print(minCoins);

    if(i < numProblems - 1) readline();
}