전력 케이블을 하수관으로

어느 지방 자치체에 여러 마을이 가까이 모여 있다. 풍력 발전 단지가 모든 마을에 전기를 공급하며, 고압 전력 케이블 망이 모든 마을을 발전 단지에 직접 또는 다른 마을을 거쳐 간접적으로 연결한다. 정전에 대비하기 위해 일부 구간에는 여분(중복)의 케이블이 추가로 설치되어 있다.

한편 하수관을 전부 교체해야 하지만 자재가 부족하다. 그래서 시장은 전력망의 연결이 끊기지 않는 범위에서 여분 케이블을 최대한 걷어내어 하수관으로 재활용하기로 했다. 즉, 남겨 둔 케이블만으로도 모든 마을이 서로 연결된 상태를 유지해야 하며, 그 조건에서 제거하는 케이블 길이의 합을 최대로 만든다. 이렇게 제거할 수 있는 여분 케이블의 총 길이는 결코 $400$ km를 넘지 않는다.

금속 공장에서는 전력 케이블 $1$ km로 하수관 $1$ m를 만들 수 있고, 하수관의 길이는 항상 $1$ m의 정수 배여야 한다. 재활용되는 케이블의 총 길이를 $S$ 미터라고 하면, 공장은 이 $S$ 미터를 길이가 양의 정수인 하수관들로 나누어 만드는 모든 방법의 수를 알고 싶어 한다. 이때 하수관들의 순서는 구분하지 않는다. 예를 들어 $S = 3$이면 방법은 길이 $3$짜리 하나, 길이 $2$짜리 하나와 길이 $1$짜리 하나, 길이 $1$짜리 셋의 세 가지다.

각 테스트 케이스마다 이러한 방법의 수를 구하라. 만약 전력망에 여분이 전혀 없어서 제거할 수 있는 케이블이 하나도 없다면 $0$을 출력한다.

첫 줄에 테스트 케이스의 수 $n$ ($0 < n \le 10000$)이 주어진다.

이어서 각 테스트 케이스는 다음과 같이 주어진다.

• 마을의 수 $m$ ($2 \le m \le 100$)이 한 줄에 주어진다.
• 전력 케이블의 수 $k$ ($1 \le k \le 1000$)이 한 줄에 주어진다.
• 다음 $k$개의 줄에는 각각 세 정수 $f_i$, $t_i$, $l_i$가 공백으로 구분되어 주어진다. 이는 마을 $f_i$ ($1 \le f_i \le m$)와 마을 $t_i$ ($1 \le t_i \le m$) 사이에 길이 $l_i$ ($1 \le l_i \le 400$) km인 전력 케이블이 있음을 뜻한다.

각 테스트 케이스마다, 어떤 마을도 전력망에서 분리되지 않도록 하면서 제거할 수 있는 최대 길이의 케이블을 재활용하여 만들 수 있는 하수관 조합의 수를 한 줄에 하나씩 출력한다. 전력망에 여분이 없어 제거할 수 있는 케이블이 없으면 $0$을 출력한다.