stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int i = 0; i < (n); i++) 

#define all(v) begin(v),end(v)

using ll = long long;



int main() {

  int n;cin>>n;

  vector<int> vec(n+1);

  for(int i=1;i<=100;i++){

    for(int j=1;j<=100;j++){

      for(int k=1;k<=100;k++){

        int ans=i*i+j*j+k*k+i*j+j*k+k*i;

        if(ans<=n)vec[ans]++;

      }

    }

  }

  for(int i=1;i<=n;i++)cout<<vec[i]<<endl;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int i = 0; i < (n); i++) 

#define all(v) begin(v),end(v)

using ll = long long;



int main() {

  int n;cin>>n;

  vector<int> ans(n+1);

  for(int x=1;x<=100;x++){

    for(int y=1;y<=100;y++){

      for(int z=1;z<=100;z++){

        int a=x*x+y*y+z*z+x*y+y*z+z*x;

        if(a>n)break;

        ans[a]++;

      }

    }

  }

  for(int i=1;i<=n;i++)cout<<ans[i]<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int i = 0; i < (n); i++) 

#define all(v) begin(v),end(v)

using ll = long long;



int main() {

  int n;cin>>n;

  vector<int> ans(n+1);

  for(int x=1;x<=100;x++){

    for(int y=1;y<=100;y++){

      for(int z=1;z<=100;z++){

        int cnt=x*x+y*y+z*z+x*y+y*z+z*x;

        if(cnt<=n)ans[cnt]++;

      }

    }

  }

  for(int i=1;i<=n;i++)cout<<ans[i]<<endl;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for (int i = 0; i < (n); i++) 

#define all(v) begin(v),end(v)

using ll = long long;



int main() {

  int n;cin>>n;

  vector<int> ans(n+1);

  for(int x=1;x<=100;x++){

    for(int y=1;y<=100;y++){

      for(int z=1;z<=100;z++){

        int a=x*x+y*y+z*z+x*y+y*z+z*x;

        if(a>n)break;

        ans[a]++;

      }

    }

  }

  for(int i=1;i<=n;i++)cout<<ans[i]<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <bits/stdc++.h>

#include<cmath>

using namespace std;



int operation(int x , int y , int z)

{

    int v = (x*x)+(y*y)+(z*z)+(x*y)+(y*z)+(x*z);

    return v;

}

int main()

{

    int n;

    cin >>n;

    int counter=0;

    for(int i =1; i<=n; i++)

    {

        for(int x=1; x<100; x++)

        {

            for(int y=1; y<100; y++)

            {

                for(int z=1; z<100; z++)

                {

                    if(i == operation(x,y,z))

                    {

                        counter++;

                    }

                    else if(i < operation(x,y,z))

                        break;



                }

            }

        }



        cout<<counter<<endl;

        counter=0;

    }



    return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <cmath>

using namespace std;



int main()

{

    int n, c, maxxyz, x, y, z, val;

    cin >> n;

    int a [n];

    for ( int i = 0; i < n; i ++) {

        a[i] = 0;

    }

    maxxyz = sqrt(n-5);

    for  ( x = 1; x <= maxxyz; x++){

            for ( y = 1; y <= maxxyz; y++) {

                for ( z = 1; z <= maxxyz; z++) {

                    val =x*x + y*y + z*z + x*y + y*z + z*x;

                    if ( val <= n) a[val-1]++;

            }

        }

    }

    for ( int i = 0; i < n; i ++) {

        cout << a[i] <<endl;

    }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <math.h>

#include <vector>

#include <string>

using namespace std;

int main() {

	int N = 0;

	scanf("%d", &N);

	vector<long>v (N+1,0);



	/*

	for (int x = 1; x <= 100; x++) {

		for (int y = 1; y <= 100; y++) {

			for (int z = 1; z <= 100; z++) {

				if ((x * x + y * y + z * z + x * y + x * z + z * y) != 0 && ((x * x + y * y + z * z + x * y + x * z + z * y) < v.size())) {

					v[(x * x + y * y + z * z + x * y + x * z + z * y) - 1]++;

				}

				

			}

			

		}

		

	}*/



	for (int i = 1; i <= 100; i++) {

		for (int w = 1; w <= 100; w++) {

			for (int y = 1; y <= 100; y++) {

				if (((i * i) + (w * w) + (y * y) + (i * w) + (i * y) + (y * w)) <= v.size()) {

					v[((i * i) + (w * w) + (y * y) + (i * w) + (i * y) + (y * w))]++;



				}



			}



		}

	}

	

	for (int i = 1; i <= N; i++) {

		string str = to_string(v[i]);

		const char* l = str.c_str();

		printf(l);

		printf("\n");

	}

	

	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

    ll equa;

    int n;

    cin>>n;

    int arr[n+1];

    for(int i=1;i<=n;i++){

        arr[i]=0;

    }

    for(int i=1;i*i<=n;i++){

        for(int j=1;j*j<=n;j++){

            for(int z=1;z*z<=n;z++){

              equa = i*i + j*j + z*z + i*j + i*z + j*z;

              if(equa>0 && equa<=n){

                  arr[equa]++;

              }

              else if(equa>n){

                  break;

              }   

            }

        }

    }

    for(int i=1;i<=n;i++){

        cout<<arr[i]<<endl;

    }

    return 0;



}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*

*         ****FOX****

*/

#include <iostream>

#include <string>

#include <algorithm>

#include <stack>

#include <queue>

#include <vector>

#include <map>

#include <set>

#include <sstream>

#include <iomanip>

#include <cmath>

#include <limits>

//freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

#include <utility>

#include <list>

#include <cstdio>

#include<forward_list>

#include<algorithm>

#include<string>

#define Omar_Hafez ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

#define pi 3.1415926536

#define ll long long

#define ull unsigned long long

#define lli long long int

using namespace std;

int main()

{

    Omar_Hafez

   int n; cin >> n;

    vector<int> v(n,0); 

    for (int i = 1; i < 400; i++)

    {

        for (int j = 1; j < 400; j++)

        {

            for (int z = 1; z < 400; z++)

            {

                int res = (i * i) + (j * j) + (z * z) + (i * j) + (j * z) + (i * z);  

                if (res <= n)  v[--res]++;

                else break;

            }

        }

    }

    for (int i = 0; i< v.size(); i++) cout << v[i] << "\n";

    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

    ll equa;

    int n;

    cin>>n;

    int arr[n+1];

    for(int i=1;i<=n;i++){

        arr[i]=0;

    }

    for(int i=1;i*i<=n;i++){

        for(int j=1;j*j<=n;j++){

            for(int z=1;z*z<=n;z++){

              equa = i*i + j*j + z*z + i*j + i*z + j*z;

              if(equa>0 && equa<=n){

                  arr[equa]++;

              }

              else if(equa>n){

                  break;

              }   

            }

        }

    }

    for(int i=1;i<=n;i++){

        cout<<arr[i]<<endl;

    }

    return 0;



}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

using namespace std;



int formula(int x,int y,int z) {

    int ans = x*x+y*y+z*z+x*y+x*z+y*z;

    return ans;

}



int main()

{

    int n;

    cin>>n;

    int x(1),y(1),z(1),formul(0),c(0);

    for (int i=1;i<=n;i++)  {

        for (int x=1;x<=99;x++) {

            for (int y=1;y<=99;y++) {

               for (int z=1;z<=99;z++) {

                    formul=formula(x,y,z);

                    if (formul==i) c++;

                    if (formul>i) break;

                }

            }

        }

        

        cout<<c<<endl;

        c=0;

    }

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define ll long long

using namespace std;

int main() {

    ll equa;

    int n;

    cin>>n;

    int arr[n+1];

    for(int i=1;i<=n;i++){

        arr[i]=0;

    }

    for(int i=1;i*i<=n;i++){

        for(int j=1;j*j<=n;j++){

            for(int z=1;z*z<=n;z++){

              equa = i*i + j*j + z*z + i*j + i*z + j*z;

              if(equa>0 && equa<=n){

                  arr[equa]++;

              }

              else if(equa>n){

                  break;

              }   

            }

        }

    }

    for(int i=1;i<=n;i++){

        cout<<arr[i]<<endl;

    }

    return 0;



}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



int main()

{



    int n, v;

    cin >> n;



    int a[10050] = {0};



    for (size_t i = 1; i <= 104; i++)

    {

        for (size_t j = 1; j <= 104; j++)

        {

            for (size_t k = 1; k <= 104; k++)

            {

                v = i*i + j*j + k*k + i*j + j*k + i*k;

                if(v < 10050)

                    a[v]++;

            }

        }

    }



    for (size_t i = 0; i < n; i++)

    {

        cout << a[i + 1] << "\n";

    }

    

    return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define int long long

using namespace std;



signed main() 

{

	int t;

	cin >> t;

	for(int i = 1; i <= t; i++){

		int cnt = 0;

		for(int x = 1; x * x <= i; x++){

			for(int y = 1; y <= x; y++){

				for(int z = 1; z <= y; z++){

					if(x*x+y*y+z*z+x*z+x*y+y*z == i){

						if(x!=y && y!=z && x!=z){

							cnt += 6;

						}

						if(x!=y && y!=z && x==z){

							cnt += 3;

						}

						if(x==y && y!=z && x!=z){

							cnt += 3;

						}

						if(x!=y && y==z && x!=z){

							cnt += 3;

						}

						if(x==y && y==z && x==z){

							cnt += 1;

						}

					}

				}

			}	

		}

		cout << cnt << '\n';

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<cstring>

#include<string>

#define inf 0x3f3f3f3f

using namespace std;

int n,m,l,a,b,c,q,s,t,dist[310][310],dis[310][310];

int main(){

	scanf("%d%d%d",&n,&m,&l);

	memset(dis,inf,sizeof(dis));

	memset(dist,inf,sizeof(dist));

	for(int i=1;i<=m;i++) scanf("%d%d%d",&a,&b,&c),dist[a][b]=dist[b][a]=c;

	for(int k=1;k<=n;k++)

	    for(int j=1;j<=n;j++)

	        for(int i=1;i<=n;i++)

	            dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

	for(int i=1;i<=n;i++)

	    for(int j=1;j<=n;j++)

	        if(dist[i][j]<=l) dis[i][j]=dis[j][i]=1;

	for(int k=1;k<=n;k++)

	    for(int j=1;j<=n;j++)

	        for(int i=1;i<=n;i++)

	            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

	scanf("%d",&q);

	for(int i=1;i<=q;i++){

	    scanf("%d%d",&s,&t);

		if(dis[s][t]!=1061109567) printf("%d\n",dis[s][t]-1);

		else printf("-1\n");

	}

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define maxx 100010

#define mp make_pair

typedef pair<long,long long> ii;

long long gas[310][310], dist[310][310];



long long n,m,l;

int main() {

	cin >> n >> m >> l;

	for(int i = 0; i <= n; i++){

		for(int j = 0; j <= n; j++){

			dist[i][j] = 1e11;

			gas[i][j] = 1e11;

		}

	}



	long long a,b,c;

	for(int i = 0; i < m; i++){

		cin >> a >> b >> c;

		gas[a][b] = c;

		gas[b][a] = c;

	}

	for(int k = 1; k <= n; k++){

		for(int i = 1; i <= n; i++){

			for(int j = 1; j <= n; j++){

				long long aux = min(gas[i][j],gas[i][k] + gas[k][j]);

				if(aux <= l) {dist[i][j] = 1; gas[i][j] = aux;}

			}

		}

	}

	for(int k = 1; k <= n; k++){

		for(int i = 1; i <= n; i++){

			for(int j = 1; j <= n; j++){

				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);	

			}

		}

	}

	long long q;

	cin >> q;

	

	long long s,t;

	for(int i = 0; i < q; i++){

		cin >> s >> t;

		if(dist[s][t] == 1e11) cout << -1 << endl;

		else cout << dist[s][t]-1 << endl;

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



pair <long long, long long> dis[310][310];



vector <pair<long long, long long>> ed[310];



void solve(long long v, long long l){

	

	priority_queue <pair<pair<long long, long long>, long long>> q;

	

	q.push(make_pair(make_pair(0, l), v));

	

	dis[v][v] = make_pair(0, l);

	

	while(!q.empty()){

		

		long long t = -q.top().first.first, c = q.top().first.second, x = q.top().second;

		

		q.pop();

		

		if(dis[v][x].first == t && dis[v][x].second == c){

			

			for(long long i = 0; i < (long long)ed[x].size(); i++){

				

				long long tx = t + (ed[x][i].second > c), cx = (ed[x][i].second > c) ? (l - ed[x][i].second) : (c - ed[x][i].second), xx = ed[x][i].first;

				

				if(cx < 0) continue;

				else if((dis[v][xx].first == -1) || ((dis[v][xx].first > tx) || ((dis[v][xx].first == tx) && (dis[v][xx].second < cx)))){

					q.push(make_pair(make_pair(-tx, cx), xx));

					dis[v][xx].first = tx;

					dis[v][xx].second = cx;

				}

			}

		}

	}

}

			

		

int main(){

	

	for(long long i = 0; i < 310; i++) for(long long j = 0; j < 310; j++) dis[i][j].first = -1;

	

	long long n, m, l;

	scanf("%lld %lld %lld", &n, &m, &l);

	

	for(long long i = 0; i < m; i++){

		long long u, v, x;

		scanf(" %lld %lld %lld", &u, &v, &x);

		

		ed[u].push_back(make_pair(v, x));

		ed[v].push_back(make_pair(u, x));

	}

	

	for(long long i = 0; i < n; i++) solve(i + 1, l);

	

	long long q;

	scanf(" %lld", &q);

	

	for(long long i = 0; i < q; i++){

		long long s, t;

		scanf(" %lld %lld", &s, &t);

		

		printf("%lld\n", dis[s][t].first);

	}

	

	return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define maxx 100010

#define mp make_pair

typedef pair<long,long long> ii;

long long gas[310][310], dist[310][310];



long long n,m,l;

int main() {

	cin >> n >> m >> l;

	for(int i = 0; i <= n; i++){

		for(int j = 0; j <= n; j++){

			dist[i][j] = 1e11;

			gas[i][j] = 1e11;

		}

	}



	long long a,b,c;

	for(int i = 0; i < m; i++){

		cin >> a >> b >> c;

		gas[a][b] = c;

		gas[b][a] = c;

	}

	for(int k = 1; k <= n; k++){

		for(int i = 1; i <= n; i++){

			for(int j = 1; j <= n; j++){

				long long aux = min(gas[i][j],gas[i][k] + gas[k][j]);

				if(aux <= l) {dist[i][j] = 1; gas[i][j] = aux;}

			}

		}

	}

	for(int k = 1; k <= n; k++){

		for(int i = 1; i <= n; i++){

			for(int j = 1; j <= n; j++){

				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);	

			}

		}

	}

	long long q;

	cin >> q;

	

	long long s,t;

	for(int i = 0; i < q; i++){

		cin >> s >> t;

		if(dist[s][t] == 1e11) cout << -1 << endl;

		else cout << dist[s][t]-1 << endl;

	}

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
// C++ 14

#include <iostream>

#include <vector>

#include <list>

#include <algorithm>

#include <queue>

#include <stack>

#include <math.h>



#define ll long long

#define Int int

#define loop(x, start, end) for(Int x = start; x < end; x++)

#define loopdown(x, start, end) for(int x = start; x > end; x--)

#define span(a,x,y) a.begin()+x,a.begin()+y

#define span_all(a) a.begin(),a.end()

#define len(x) (x.size())

#define last(x) (*(x.end()-1))



using namespace std;



#define MAX_N 301

#define MAX_Q (301*300)

#define MAX_C 1000000001



Int N, M, Q;

vector<Int> S(MAX_Q, -1), T(MAX_Q, -1);

ll L;



ll G[MAX_N][MAX_N];

ll COUNT[MAX_N][MAX_N];



void apsp(ll g[MAX_N][MAX_N]) {

  loop(k,0,N) {

    loop(u,0,N) {

      if (g[u][k] == MAX_C) continue;

      loop(v,0,N) {

        if (g[k][v] == MAX_C) continue;

        g[u][v] = min(g[u][v], g[u][k] + g[k][v]);

      }

    }

  }

}



void dump(ll g[MAX_N][MAX_N]) {

  loop(n,0,N) {

    loop(m,0,N) {

      cout << g[n][m] << " ";

    }

    cout << endl;

  }

}



void solve() {

  apsp(G);

  loop(n,0,N) {

    loop(m,0,N) {

      if (G[n][m] <= L) COUNT[n][m] = 1;

    }

  }

  apsp(COUNT);

  loop(q,0,Q) {

    if (COUNT[S[q]][T[q]] == MAX_C) cout << -1 << endl;

    else cout << COUNT[S[q]][T[q]] - 1 << endl;

  }

}



int main() {

  Int a, b;

  ll c;

  cin >> N >> M >> L;

  loop(n,0,N) {

    loop(m,0,N) {

      G[n][m] = COUNT[n][m] = (n == m) ? 0 : MAX_C;

    }

  }

  

  loop(m,0,M) {

    cin >> a >> b >> c;

    G[a-1][b-1] = c;

    G[b-1][a-1] = c;

  }

  

  cin >> Q;

  loop(q,0,Q) {

    cin >> S[q] >> T[q];

    S[q]--;

    T[q]--;

  }

  

  solve();

}

// Optimized solution to the same problem (faster):
// C++ 14

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

void solve(); int main() { solve(); return 0; }



const ll INF = 1000000000000000000;

int n,m,l;

ll D[305][305];

ll D2[305][305];

void asap(ll G[305][305]) {

  loop(k,0,n) {

   loop(u,0,n) {

     if (G[u][k] == INF) continue;

     loop(v,0,n) {

       if (G[k][v] == INF) continue;

       G[u][v] = min(G[u][v], G[u][k] + G[k][v]);

     }

   }

  }

}



void solve() {

  cin >> n>>m>>l;

  loop(i,0,n+1) loop(j,0,n+1) D[i][j] = D2[i][j] = INF;

  loop(i,0,m) {

    int a, b, c;

    cin >> a >> b >> c;

    a--;b--;

    D[a][b] = D[b][a] = c;

  }

  

  asap(D);

  

  loop(i,0,n) loop(j,0,n) {

    if (D[i][j] <= l) D2[i][j] = 1;

  }

  

  asap(D2);

  

  int q;

  cin >> q;

  loop(i,0,q) {

    int s, t;

    cin >> s >> t;

    s--;t--;

    if (D2[s][t]==INF) { cout << -1 << endl; continue; }

    cout << D2[s][t] -1 << endl;

  }

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



typedef long long lint;

const lint N = 330, INF = 1e17+7;



lint n, m, l, dist[N][N], fuel[N][N], ans[N][N];





int main(){

#ifdef LOCAL

	freopen("input", "r", stdin);

#endif

	scanf("%lld %lld %lld", &n, &m, &l);



	for (int i = 0; i < N; i++){

		for (int j = 0; j < N; j++){

			if (i==j)

				continue;

			dist[i][j] = INF;

			fuel[i][j] = INF;

		}

	}



	for (lint i = 0; i < m; i++){

		lint a, b, c;

		scanf("%lld %lld %lld", &a, &b, &c);

		dist[a][b] = dist[b][a] = c;

	}





	for (int k = 1; k <= n; k++){

		for (int i = 1; i <= n; i++){

			for (int j = 1; j <= n; j++){

				if (i == j)

					continue;

				if (dist[i][k] + dist[k][j] < dist[i][j]){

					dist[i][j] = dist[i][k] + dist[k][j];

				}

			}

		}

	}



	for (int i = 1; i <= n; i++){

		for (int j = 1; j <= n; j++){

			if (i == j)

				continue;

			if (dist[i][j] <= l)

				fuel[i][j] = 1;

		}

	}



	for (int k = 1; k <= n; k++){

		for (int i = 1; i <= n; i++){

			for (int j = 1; j <= n; j++){

				if (fuel[i][k] + fuel[k][j] < fuel[i][j])

					fuel[i][j] = fuel[i][k] + fuel[k][j];

			}

		}



	}



	lint q;



	scanf("%lld", &q);



	while (q--){

		lint s, t;

		scanf("%lld %lld", &s, &t);

		

		if (fuel[s][t] < INF)

			printf("%lld\n", fuel[s][t] - 1);

		else

			printf("-1\n");



	}



	return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define sigma_size 30

#define max_size (int)(2e5+10)

#define MAX (int)(1e5+7)

int qread()

{

	char c; int s=0,t=1; while ((c=getchar())<'0' || c>'9') (c=='-' && (t=-1));

	do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s*t;

}



int n , m , l;

LL dp[305][305] , cnt[305][305];

const LL inf = 1ll << 60;

int ans[max_size] , tot = 0;

int main ()

{

	cin >> n >> m >> l;

	for ( int i = 1 ; i <= n ; i++ )

		for ( int j = 1 ; j <= n ; j++ )

			if ( i == j ) dp[i][j] = 0;

			else dp[i][j] = inf;

	for ( int i = 1 ; i <= m ; i++ ){

		LL a , b , c;

		cin >> a >> b >> c;

		if ( c <= l && c < dp[a][b] )

			dp[a][b] = dp[b][a] = c;

	}

	for ( int k = 1 ; k <= n ; k++ )

		for ( int i = 1 ; i <= n ; i++ )

			for ( int j = 1 ; j <= n ; j++ )

				dp[i][j] = min ( dp[i][j] , dp[i][k] + dp[k][j] );

	for ( int i = 1 ; i <= n ; i++ )

		for ( int j = 1 ; j <= n ; j++ )

			if ( i == j ) continue;

			else

			{

				if ( dp[i][j] <= l ) cnt[i][j] = 1;

				else cnt[i][j] = inf;

			}

	for ( int k = 1 ; k <= n ; k++ )

		for ( int i = 1 ; i <= n ; i++ )

			for ( int j = 1 ; j <= n ; j++ )

				cnt[i][j] = min ( cnt[i][j] , cnt[i][k]+cnt[k][j] );

	int q;

	cin >> q;

	while (q--)

	{

		int s , t;

		cin >> s >> t;

		if ( cnt[s][t] == inf ) ans[tot++] = -1;

		else ans[tot++] = cnt[s][t]-1;

	}

	for ( int i = 0 ; i < tot ; i++ )

		cout << ans[i] << endl;

}

// Fastest known solution for this problem: