"Nhất tiễn" BaoJiaoPisu là tài năng trẻ được kì vọng của đội Tin Đà Nẵng. BaoJiaoPisu đang tập luyện hăng say để chuẩn bị màn combat code với "Song điêu" của Tam Kì. Nhưng vì đang mơ tưởng đến chiến thắng trước mắt, BaoJiaoPisu không thể tập trung cho bài tập về nhà của Facebook được. Các bạn hãy giúp BaoJiaoPisu hoàn thành bài tập này sớm để cậu có thể thoải mái tập trung cho trận combat sắp tới nhé.

Trong 1 group trên Facebook có \(n\) người, \(m\) cặp bạn khác nhau. Cho \(q\) truy vấn, mỗi truy vấn gồm 2 số \(s, t\). Ở mỗi truy vấn, hãy cho biết số bạn chung của 2 người \(s, t\) là bao nhiêu?

Input

• Dòng đầu tiên gồm 2 số nguyên \(n\), \(m\) (\(n \leq 1000\), \(m \leq \dfrac{n(n - 1)}{2}\))
• M dòng tiếp theo, mỗi dòng gồm 2 số \(u, v\) thể hiện 2 người \(u, v\) là bạn bè của nhau
• Dòng tiếp theo gồm số nguyên \(q\) (\(q \leq 1000\))
• Q dòng tiếp theo, mỗi dòng gồm 2 số nguyên \(s, t\) (\(1 \leq s, t \leq n\))

Output

In ra \(Q\) dòng, mỗi dòng là kết quả của truy vấn thứ \(i\)

Example

Sample Input

5 4
5 3
2 5
1 4
5 1
2
5 3
4 5

Sample Output

0
1