Một lớp học có \(n\) học sinh, được đánh số từ \(1\) đến \(n\).

Thầy chủ nhiệm muốn tổ chức một trò chơi đòi hỏi các học sinh tham gia phải rất hiểu nhau.
Thầy biết cặp học sinh (i, j) nào hiểu nhau (hiểu là quan hệ hai chiều: \(i\) hiểu \(j\) thì \(j\) cũng hiểu \(i\)).

Với mỗi bộ ba số nguyên \(a\), \(b\), \(k\), nhóm học sinh được chọn phải thỏa mãn các điều kiện:

1. Chỉ chọn từ các học sinh có số hiệu trong đoạn \([a, b]\).
2. Mỗi học sinh trong nhóm được chọn phải có ít nhất \(k\) người trong nhóm hiểu mình.
3. Số lượng học sinh trong nhóm là nhiều nhất có thể.

Dữ liệu vào

• Dòng đầu tiên: Hai số nguyên \(n\), \(m\) — số học sinh và số cặp hiểu nhau.
• \(m\) dòng tiếp theo: mỗi dòng gồm hai số nguyên \(i\), \(j\) — học sinh \(i\) và \(j\) hiểu nhau (\(i ≠ j\)).
• Một số dòng tiếp theo chứa các truy vấn. Mỗi dòng là một bộ ba số nguyên \(a\), \(b\), \(k\).

Dữ liệu ra

• Với mỗi truy vấn \((a, b, k)\), in ra một dòng là số lượng học sinh nhiều nhất có thể chọn thỏa mãn điều kiện.

Ràng buộc

• 30% số test: \(n ≤ 20\), \(m ≤ 100\), \(T = 1\)
• 30% số test: \(n ≤ 10^4\), \(m ≤ 10^5\), \(k = 1\), \(T ≤ 3\)
• 30% số test: \(n ≤ 10^4\), \(m ≤ 10^5\), \(T = 1\)
• 10% số test: \(n ≤ 10^5\), \(m ≤ 10^5\), \(T ≤ 300\)

Input 1

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

Output 1

3
0