레몬 왕국에는 개의 도시와 개의 도로가 있다. 번째 도로는 번 도시와 번 도시를 연결하는 양방향 도로이다. 단, 이며, 두 도시 사이에 여러 개의 도로가 존재할 수 있다. 하지만 현재 모든 도로는 노후화되어 사용할 수 없다.
기술자 재원이는 이 중 일부 도로를 정비하여 활성화하려 한다. 그런데 레몬 왕국의 왕 담유 18세는 도시의 형태가 원형이 되기를 원한다. 즉, 왕국을 정점 개의 무향 그래프로 보았을 때, 각 연결 성분이 다음 조건 중 하나를 만족해야 한다.
재원이는 담유의 명령을 따라야 하며, 비용 절감을 위해 연속된 번호의 도로들만 선택해 활성화하려 한다. 즉, 어떤 정수 쌍 을 정해 번 도로부터 번 도로까지의 도로만을 활성화한다.
하지만 모든 경우를 직접 시도해 보면 비용이 크므로, 그는 정보과학 전문가 우현이에게 시뮬레이션을 부탁했다. 번째 질문에서는, 를 만족하는 순서쌍 중 조건을 만족하는 경우의 수를 구해야 한다.
당신이 우현이가 되어, 각 질문에 대한 답을 구해보자.
입력은 다음과 같은 형식으로 주어진다.
첫째 줄부터 개의 줄에 걸쳐 각 질문에 대한 답을 한 줄에 하나씩 출력한다.
| 3 | 54 | 추가적인 제약 조건이 없다. |
