#include <bits/stdc++.h>

using namespace std;

int n,m,k;
int d[210][210];

void fl()
{
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++)
        {
            for(int q = 1;q <= n;q ++)
            {
                d[j][q] = min(d[j][q],d[j][i] + d[i][q]);
            }
        }
    }
}

int main()
{
    cin >> n >> m >> k;

    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= n;j ++)
        {
            if(i == j) d[i][j] = 0;
            else d[i][j] = 0x3f3f3f3f;
        }
    }

    while(m --)
    {
        int a,b,c;

        cin >> a >> b >> c;

        d[a][b] = min(d[a][b],c);

    }

    fl();

    while(k --)
    {
        int x,y;
        cin >> x >> y;
        if(d[x][y] > 0x3f3f3f3f / 2 ) cout << "impossible" << endl;
        else cout << d[x][y] << endl;
    }
    return 0;

}

#include <bits/stdc++.h>

using namespace std;


const int N = 1e5 + 10;
int n,m,k;

int dist[N],back[N];

struct st{
    int a,b,w;
};
st edge[N];


void bf()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

    for(int i = 0;i < k;i ++)
    {
        memcpy(back,dist,sizeof dist);

        for(int j = 0;j < m;j ++)
        {
            int A = edge[j].a,B = edge[j].b,W = edge[j].w;

            dist[B] = min(dist[B],back[A] + W);
        }
    }

    if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
    else cout << dist[n] << endl;
    return;

}


int main()
{
    cin >> n >> m >> k;

    for(int i = 0;i < m;i ++)
    {
        cin >> edge[i].a >> edge[i].b >> edge[i].w;
    }

    bf();
    return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

char g[N][N];
bool st[N][N];

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int n;
        bool flag = false;
        cin >> n;
        for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < n;j ++)
            {
                cin >> g[i][j];
            }
        }
        int xa,ya,xb,yb;
        cin >> xa >> ya >> xb >> yb;

        if(g[xa][ya] == '#' || g[xb][yb] == '#') 
        {
            cout << "NO" << endl;
            continue;
        }

        memset(st,false,sizeof st);

        queue<pair<int,int>> q;

        q.push({xa,ya});

       // st[xa][xb] = true;

        while(q.size())
        {
            auto t = q.front();
            q.pop();

            if(t.first == xb && t.second == yb)
            {
                flag = true;
                break;
            }

            for(int i = 0;i < 4;i ++)
            {
                int dx[4] = {0,-1,0,1},dy[4] = {1,0,-1,0};
                int ta = t.first + dx[i],tb = t.second + dy[i];
                if(ta < 0 || ta >= n || tb < 0 || tb >= n) continue;
                if(st[ta][tb]) continue;
                if(g[ta][tb] == '#') continue;

                q.push({ta,tb});
                st[ta][tb] = true;
            }
        }

        if(flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

const int N = 20;

bool st[N][N];
int res;
int n,m,x,y;

void dfs(int a,int b,int cnt)
{
    if(cnt == n * m)
    {
        res ++;
        return;
    }

    for(int i = 0;i < 8;i ++)
    {
        int dx[8]={-2,-2,-1,1,2,2,1,-1},dy[8]={-1,1,2,2,1,-1,-2,-2};

        int ta = dx[i] + a,tb = dy[i] + b;

        if(ta < 0 || ta >= n || tb < 0 || tb >= m) continue;

        if(st[ta][tb]) continue;

        st[ta][tb] = true;
        dfs(ta,tb,cnt + 1);
        st[ta][tb] = false;

    }
}

int main()
{
    int T;
    cin >> T;
    while(T --)
    {

        cin >> n >> m >> x >> y;

        res = 0;

        memset(st,false,sizeof st);

        st[x][y] = true;

        dfs(x,y,1);

        cout << res << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int m,n;
char g[30][30];

int startx,starty;

int dx[4] = {0,-1,0,1},dy[4] = {1,0,-1,0};

int cnt;
bool st[30][30];

void dfs(int x,int y)
{
    g[x][y] = '#';

    cnt ++;

    for(int i = 0;i < 4;i ++)
    {
        int tx = dx[i] + x,ty = dy[i] + y;

        if(tx >= n || tx < 0 || ty >= m || ty < 0 || g[tx][ty] == '#')  continue;

        st[tx][ty] = 1;
        dfs(tx,ty);
        st[tx][ty] = 0;

    }
    return;
}

int main()
{
    while(cin >> m >> n,m||n)
    {
        cnt = 0;

        for(int i = 0;i < n;i ++)
        {
            for(int j = 0;j < m;j ++)
            {
                cin >> g[i][j];

                if(g[i][j] == '@')
                {
                    startx = i;
                    starty = j;
                }
            }
        }
        st[startx][starty] = 1;

        dfs(startx,starty);

        cout << cnt << endl;
    }

    return 0;
}

#include <iostream>

using namespace std;
long long cnt;
bool check(long long x)
{
    if(x == 1) return false;
    if(x == 2) return true;
    for(long long i = 2;i * i <= x;i ++)
    {
        if(x % i == 0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 1;i <= n;i ++)
    {
        if(check(i))
        {
            cnt ++;
        }
    }

    cout << cnt << endl;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int n,k;
vector<int> v;

bool check(int x)
{
    if(x == 1) return false;
    if(x == 2) return true;
    for(int i = 2;i * i <= x;i ++)
    {
        if(x % i== 0) return false;
    }
    return true;
}

void function(int a)
{
    for(int i = 1;i <= a;i ++)
    {
        if(check(i))
        {
            v.push_back(i);
        }
    }
}

int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> n >> k;
        int cnt = 0;
        for(int i = 2;i <= n;i ++)
        {
           if(check(i))
           {
              function(i);
              for(int j = 0;j < v.size() - 1;j ++)
              {
                if(v[j] + v[j + 1] + 1 == i)
                {
                    cnt ++;
                }
              }

           }
           v.clear();
        }
       // cout << cnt << endl;

        //v.clear();
        if(cnt >= k) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int a,b;
        cin >> a >> b;
        cout << __gcd(a,b) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main
{
    public static void main(String [] args)
    {
        Scanner sc = new Scanner(System.in);
        double x = 3.14159;
        double r = sc.nextDouble();
        System.out.printf("A=%.4f",x * r * r);
    }
}

import java.util.Scanner;

public class Main
{
    public static void main(String [] args)
    {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt(),c = sc.nextInt(),d = sc.nextInt();
        System.out.printf("DIFERENCA = %d", a * b - c * d);
    }
}