void merge(vll &L, vll &R, vll &A){
	ll i=0,j=0,k=0,iL,jL;
	iL = L.size();
	jL = R.size();
	while(i<iL && j<jL ){
		if(L[i]<=R[j]){
			A[k] = L[i];
			i++;
		}
		else if(R[j]<=L[i]){
			A[k] = R[j];
			j++;
		}
		k++;
	}
	while(i<iL){
			A[k] = L[i];
			i++;
			k++;
	}
	
	while(j<jL){
			A[k] = R[j];
			j++;
			k++;
	}
	
	return;
}

vll matmul(const vll &A, const vll &B) {
    int m = A.size();
    int n = B[0].size();
    int x = B.size();
    vll C(m, vector<long long>(n, 0));
    
    for (int i=0; i<m; ++i) {
        for (int j=0; j<n; ++j) {
            for (int k=0; k<x; ++k) {
                C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % mod;
            }
        }
    }
    
    return C;
}

int main(){
	ll n,m,u,v,c;
	while(cin >> n >> m && (n||m)){
		
		s=1,t=n+1; N=n+2; pi.assign(N,INF);
		cap.assign(N,vll(N,0)); flow.assign(N,vll(N,0)); cost.assign(N,vll(N,0));

		vector<ll> U,V,C; 
		for(int i=0 ; i<m ; i++){
			cin >> u >> v >> c;
			U.push_back(u); V.push_back(v); C.push_back(c);

		}
		ll D, K; cin >> D >> K;
		for(int i=0 ; i<m ; i++){
			u=U[i] , v=V[i], c= C[i];
			cost[u][v]=c; cost[v][u]=c;
			 cap[u][v]=K;  cap[v][u]=K;
		}
		cap[n][t]=D; cost[n+1][t]=0;
		mincost=0; maxflow=0; MCMF();
		if(maxflow==D) cout << mincost << endl;
		else cout << "Impossible." << endl;
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);
	int T;
	ll a, b;
	cin >> T;
	preprocess();
	 while(T--){
		cin >> a >> b;
		if(a == b){
			cout << test(a) << '\n';
			continue;
		}
		vll::iterator first = lower_bound(nums.begin(), nums.end(),a), last = lower_bound(nums.begin(), nums.end(),b);
		cout << (int)(last - first) + (*last == b) << '\n';
		
	}
}

vll mul(const vll & va, const vll & vb) {
  int len = 32 - __builtin_clz(std::max(va.size(), vb.size()) - 1);
  len = 1 << (len + 1);
  vcd a(len), b(len);
  for (int i = 0; i < (int)va.size(); i++) a[i] = cd(va[i], 0);
  for (int i = 0; i < (int)vb.size(); i++) b[i] = cd(vb[i], 0);
  a = fft(a);
  b = fft(b);
  for (int i = 0; i < len; i++) {
    double real = a[i].real() * b[i].real() - a[i].imag() * b[i].imag();
    a[i].imag() = a[i].imag() * b[i].real() + b[i].imag() * a[i].real();
    a[i].real() = real;
  }
  a = fft(a, true);
  vll res(len);
  for (int i = 0; i < len; i++) res[i] = (long long)(a[i].real() + 0.5);
  return res;
}

ll solve(vll dat)
{
    
    int sz=dat.size();
    for(int i=1;i<sz;i++)
    {
        if(i==1)
            dat[i]=max(dat[i-1], dat[i]);
        else
            dat[i]=max(dat[i-1], dat[i]+dat[i-2]);
    }
    return dat[sz-1];
}

void all( vll& v, vll& l )
{
	for( int i = 0; i < v.size(); ++i )
	{
		vll tmp, comb;
		for( vlli j = l.begin(); j != l.end(); ++j )
			tmp.push_back( *j + v[ i ] );
		for( vlli m = l.begin(), n = tmp.begin(); m != l.end() || n != tmp.end(); )
			comb.push_back( n == tmp.end() || m != l.end() && *m <= *n? *m++ : *n++ );
		l.swap( comb );
	}
}

vll matexp(vll A, int n) {
    int m = A.size();
    vll ret = matunit(m);

    while (n > 0) {
        if (n & 1) {
            ret = matmul(ret, A);
        }
        A = matmul(A, A);
        n >>= 1;
    }

    return ret;
}

vll matadd(const vll &A, const vll &B) {
    int m = A.size();
    int n = A[0].size();
    vll C(m, vector<long long>(n, 0));
    for (int i=0; i<m; ++i) {
        for (int j=0; j<n; ++j) {
            C[i][j] = A[i][j] + B[i][j];
            if (C[i][j] >= mod) {
                C[i][j] -= mod;
            }
        }
    }
    
    return C;
}

vll merge_sort(vll S){
	vll tempL,tempR;
	ll len = S.size();
	if(len < 2 )
		return S;	// array is already sorted. Base case
	rep(i,len/2)
		tempL.pub(S[i]);
	repk(i,len/2,len)
		tempR.pub(S[i]);
	tempL = merge_sort(tempL);
	tempR = merge_sort(tempR);
	merge(tempL,tempR,S);
	return S;

}

    static vll karatsubaMultiply(const vll &a, const vll &b) {
        int n = a.size();
        vll res(n + n);
        if (n <= 32) {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    res[i + j] += a[i] * b[j];
            return std::move(res);
        }

        int k = n >> 1;
        vll a1(a.begin(), a.begin() + k);
        vll a2(a.begin() + k, a.end());
        vll b1(b.begin(), b.begin() + k);
        vll b2(b.begin() + k, b.end());

        vll a1b1 = karatsubaMultiply(a1, b1);
        vll a2b2 = karatsubaMultiply(a2, b2);

        for (int i = 0; i < k; i++)
            a2[i] += a1[i];
        for (int i = 0; i < k; i++)
            b2[i] += b1[i];

        vll r = karatsubaMultiply(a2, b2);
        for (int i = 0; i < (int)a1b1.size(); i++)
            r[i] -= a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            r[i] -= a2b2[i];

        for (int i = 0; i < (int)r.size(); i++)
            res[i + k] += r[i];
        for (int i = 0; i < (int)a1b1.size(); i++)
            res[i] += a1b1[i];
        for (int i = 0; i < (int)a2b2.size(); i++)
            res[i + n] += a2b2[i];
        return std::move(res);
    }

bool in_lookup(const vll &l, long long n) // Lookup table method
{
    return std::find(l.begin(), l.end(), n) != l.end();
}

void preprocess(){
	nums.push_back(0);
	ll sqr = 1, i = 1;
	while(sqr <= max_n){
		if(test(sqr) && sqr%i == 0) nums.push_back(sqr);
		i++; sqr = i*i;
	}
}

ll cal() {
    vec.push_back(0);
    vec.push_back(1);
    ll add = 2;
    ll a = 2;
    for (int i = 2; i < 1000001; ++i) {
        vec.push_back(vec[i - 1] + a);
        i++;
        a += add;
        vec.push_back(vec[i - 1] + a);
        a += add;
        add++;
    }
}

void gen(void)
{
    LL i,j,k;
    for(i=1;i<=1005;i++) arr[i]=i*i*i;
    for(i=1; i<=1005; i++)
    {
        for(j=i+1; j<=1005; j++)
        {
            k=arr[i]+arr[j];
            mp[k]++;
            if(mp[k]==2) cont.pb(k);
        }
    }
    sort(cont.begin(),cont.end());
    return;
}

void init()
{
    int i=0 , j;

    LL pnum=0 , p=1;

    sll st;
    sll::iterator it;

    for(i=0; i<plen; i++)
    {
        pnum = prm[i];

        for(j=2; j<=40; j++)
        {
           //pnum = power(prm[i] , j);

           p=1;

           for(int k=1; k<=j; k++)
           {
               p*=pnum;

               if(p > mxhigh) break;
           }

           if(p < mxhigh)
           {
               st.insert(p);
           }
        }
    }

    //cerr << st.size();

    for(it=st.begin() ; it!=st.end() ; ++it)
    {
        v.push_back(*it);
    }

    //for(i=0; i<100; i++) cout << v[i] << " ";
    //cout << v.size();
    //cout << v[v.size()-1];
    vlen = v.size();
}

ll dijkstra(int s, int t){
	found.assign(N,0); dist.assign(N,INF); f.assign(N,0); dad.assign(N,pii(-1,2));
	dist[s]=0; f[s]=INF;
	while(s!=-1){
		int best=-1; found[s]=true;
		for(int k=0 ; k<N; k++){
			if(found[k]) continue;
			relax(s,k,cap[s][k]-flow[s][k],cost[s][k],1);
			relax(s,k,flow[k][s],-1*cost[k][s],-1);
			if(best==-1 || dist[k]<dist[best]) best=k;
		}
		s=best;
	}
	for(int k=0 ; k<N ; k++){
		pi[k]=min(pi[k]+dist[k],INF);
	}
	return f[t];
}

void prec()
{
    ll i,j,k,l;
    for(i=1; i<INT_MAX; i*=2)
        for( j=i; j<INT_MAX; j*=3)
            for( k=j; k<INT_MAX; k*=5)
                for( l=k; l<INT_MAX; l*=7)
                    num.pb(l);
    sort(all(num));
}

int main ()
{
	ll mid;

	ll i,j,k,x,ans=0,depend,l,n,ind;
	
	cin>>n>>m>>depend;
	fr(i,n)
	{
		cin>>x;
		man.push_back(x);
	}

	int count(int n, int k) {
        K = k;
        T.assign(27, vector<long long>(27, 0));
        int start_row = 0;
        for (int j=1; j<27; ++j) {
            T[start_row][j] = 27-j;
            T[++start_row][j] = j;
        }
        if (n & 1) {
            return ((n>1 ? S((n-1)/2) : 0) + S((n+1)/2)) % mod;
        } else {
            return 2*S(n/2) % mod;
        }
	}