Once upon a time, there was a noble rook called Danny who lived in a normal 8x8 chessboard. All squares lived in peace and Danny was a joyful rook, moving either vertically or horizontally across the board, never going off limits. Oh boy did he enjoy moving! He spent all days visiting the 64 squares and bringing flowers and other gifts to them. All squares loved Danny very much, even though they felt sorry for him because there was no Rookette for him to date.

The King took notice of the squares’ gossiping and he did something very remarkable. He arranged Danny a date with María, a Rookette from another chessboard. So, María stepped in one of the squares and Danny went immediately after her. However, the King made sure it wasn’t easy for Danny. He told him:

“Danny, I love you very much. We all do. What I am doing right now is because I love you.”

Danny was perplexed, without a clue. “What do you mean, Oh righteous King?”

Suddenly, the King arranged M bombs in M squares. “In life, you must work hard to achieve your dreams. I cannot just hand María over to you. You need to earn your right to date her.”

“Oookkkk…” said Danny, in a doubtful tone.

“I may also step in one of the squares. Go after her!”

And off went Danny. Assume Danny is very desperate to meet her, so he will try to get to her in the shortest possible way. The King  wants to prolong Danny’s path (maybe to have him think thoroughly about becoming a man). The King needs to decide where he will step in, he has N empty squares to choose from.

Write a program that outputs the length of the path should both Danny and the King act optimally. There will always be a path.

Input

There is a single test case per input file. The first 8 lines contain 8 characters each, and they represent the initial state of the chessboard. The lines are enumerated from 0 to 7 and so are the 8 characters of each line. The character at position (i, j)  can be one of the following:

• ‘.’ : an empty square.
• ‘#’ : a bomb.
• ‘?’ : the princess.
• '$' : Danny.

The following line contains N (0 <= N <= 10), representing the number of empty squares the King has to choose from. Then follow N lines. Each of these lines contain two integers Xi, Yi (0 <= Xi, Yi <= 7), the position of an empty square.

Output

Write a single line containing the length of the path Danny takes to reach María, if both Danny and the King act optimally.

Sample

Input
$......?
########
########
########
########
########
########
#######.
1
7 7

Output
7