1. 

/**
* FWP, Ausgew¤hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: 10306 - e-Coins
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=15&problem=1247&mosmsg=Submission+received+with+ID+8027306
*
* @author Evgeni Pavlidis
* @version 1.0, 06/08/2010
*
* Method : Memoization
* Status : Accepted
* Runtime: 0.464
*/

import java.io.*;
import java.util.*;

class Main {

private static long coins, S;
private static long[][] coin;
private static Map<Long, Long> cache = new HashMap<Long, Long>();

private static long topDown(long X, long Y)
{
if(cache.containsKey((X << 20) + Y))
return cache.get((X << 20) + Y);

if(X*X + Y*Y > S)
return -1;

if(X*X + Y*Y == S)
return 0;

long current, result = Long.MAX_VALUE;
for(int c = 0; c < coins; c++)
{
current = topDown(X + coin[c][0], Y + coin[c][1]) + 1;

if(current > 0 && current < result)
result = current;
}

cache.put(((X << 20) + Y), result);
return result;
}



public static void main(String ...args)
{
Scanner sc = new Scanner(System.in);
int testCases = sc.nextInt();

for(int tc = 0; tc < testCases; tc++)
{
coins = sc.nextInt();
S = sc.nextInt();

cache.clear();
coin = new long[(int)coins][2];

for(int c = 0; c < coins; c++)
{
coin[c][0] = sc.nextInt();
coin[c][1] = sc.nextInt();
}

S = S*S;
long result = topDown(0,0);

System.out.println( ((result == Long.MAX_VALUE)? "not possible" : result) );
}
}
}