시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB76427119940.530%

문제

"마, 내가 누군지 아나? 저커버그가 내 후임이다."

준원이는 저커버그와 함께 페이스북을 만들던 리즈시절을 회상하곤 한다... 저커버그가 페이스북을 다 만들기 직전, 바로 그 순간 저커버그에게 급똥이 찾아왔다. 그는 마지막 남은 기능 하나를 준원이에게 맡겼고, 그 기능이 바로 '함께 아는 친구' 기능이었다.

페이스북의 사용자는 총 N명이고, 각 사용자는 1번에서 N번까지로 번호 붙어 있었다. 준원이는, 사용자의 친구관계에 대한 정보가 모두 주어졌을 때,

"a번 사용자, b번 사용자와 공통적으로 친구 관계인 사용자의 수"

를 묻는 Q개의 질문에 차례로 답해야 했다.

준원이는 천하코일제딩대회 참가자 여러분에게 이 기능을 외주 맡겼다. 여러분이 이 기능을 대신 구현하면, 준원이는 여러분이 천하코일대딩제회에서 맞은 문제를 몰래 하나 늘여주겠다고 한다. 어떤가?

입력

첫째 줄에, 사용자의 수를 나타내는 정수 N이 주어진다.

이후 N개의 줄에 걸쳐, 각 사람의 친구관계를 나타내는 길이 N의 문자열이 N개 주어진다. i번째 줄의 j번째 문자는, i번 사용자가 j번 사용자와 친구일 때에 1, 아닐 때에 0이다.

이후, 질문의 개수를 나타내는 정수 Q가 주어진다.

이후 Q개의 줄에 걸쳐, 질문을 나타내는 두 정수 a와 b가 공백을 사이에 두고 주어진다.

출력

Q개의 줄에 걸쳐, 각 질문에 대한 답을 나타내는 정수를 하나씩 차례대로 출력한다.

제한

  • 2 ≤ N ≤ 2,000
  • 친구 관계는 대칭적이다. 즉, i번 사용자가 j번 사용자와 친구이면, j번 사용자는 i번 사용자와 친구이다.
  • 자기 자신과 친구인 사용자는 없다.
  • 1 ≤ Q ≤ 500,000
  • 1 ≤ a, b ≤ N
  • a ≠ b

예제 입력 1

4
0110
1011
1100
0100
3
2 4
1 3
1 4

예제 출력 1

0
1
1

예제에서, 1, 2번 사용자, 1, 3번 사용자, 2, 3번 사용자, 2, 4번 사용자는 서로 친구이다. 

이 때, 

  • 2번 사용자, 4번 사용자와 동시에 친구인 사용자는 없다.
  • 1번 사용자, 3번 사용자와 동시에 친구인 사용자는 2번 사용자 1명이다.
  • 1번 사용자, 4번 사용자와 동시에 친구인 사용자는 2번 사용자 1명이다.

노트

입출력 양이 많다. 느린 입출력 함수를 쓰면 입력 받는 데에 걸리는 시간만으로 시간 초과가 발생할 수 있으므로 유의하라.

  • C++에서는, cin, cout 함수를 가급적 쓰지 말고, scanf, printf 함수로 입출력을 진행하는 편이 좋다.
  • Java에서는, Scanner 클래스 대신, BufferedReader 클래스를 사용하여 입력받는 편이 좋다.
  • Python에서는, input 함수를 쓰는 대신, import sys를 코드의 앞 부분에서 선언하면 같은 역할을 하는 더 빠른 함수인 sys.stdin.readline을 쓸 수 있다.