Facebook

• a,b가 주어졌을때 공통된 이웃을 그냥 세려면 O(N)이 걸리지만, 비트셋을 이용하면 O(N/w)로 단축시킬수 있다. 그래프에서 삼각형 세기에서도 설명한 방법이다. 이렇게 하면 총 시간복잡도는 O(QN/w)가 된다.
• 입력을 비트셋으로 변환할때에는 그냥 입력 자체가 2진수라고 생각해서, 바로 int함수를 써서 변환하면 간단하다

"""Solution code for "BOJ 20501. Facebook".

- Problem link: https://www.acmicpc.net/problem/20501
- Solution link: http://www.teferi.net/ps/problems/boj/20501

Tags: [bitset]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    friends = [int(sys.stdin.readline(), 2) for _ in range(N)]
    Q = int(sys.stdin.readline())
    for _ in range(Q):
        a, b = [int(x) - 1 for x in sys.stdin.readline().split()]
        print((friends[a] & friends[b]).bit_count())


if __name__ == '__main__':
    main()