Here You need to implement Dijkstra's Algorithm(Single Source Shortest Path Algorithm).

You will be given an adjacency matrix of an undirected graph and some q queries.

Each query contains two integers(0-indexed) denoting the source and destination vertices. 

For every query you need to print the shortest path between the given two vertices.

Input:

First line contains integer n denoting the number of vertices in the graph.

Next n lines contains n integers denoting nxn adjacency matrix a,the value a[ i ] [ j ] denotes the distance between ith and jth vertex.

Next line contains integer q denoting number of queries.

Next q lines contains two integers denoting source and destination vertices

Output:

Output the q lines denoting the shortest path between two vertices given in each respective query.

Constraints:

1 <=  n <= 9

1 <= q <= n

1<= a[i][j] <= 100000.