Các ninja làng IOI cần giết ~n~ người tại ~n~ địa điểm khác nhau được đánh dấu từ ~1~ đến ~n~. Các địa điểm được nối với nhau bởi ~m~ con đường ~1~ chiều. Mỗi ninja có thể xuất phát từ một địa điểm nào đó đi trên một lộ trình nào đó và giết sạch những người trên lộ trình đấy (lộ trình có thể rất lòng vòng). Hỏi cần tối thiểu bao nhiêu ninja để có thể hoàn thành nhiệm vụ.

Input

Dòng đầu tiên là số testcase, ~T \leq 70~.

Mỗi case bắt đầu bằng một dòng trống, dòng thứ 2 ghi 2 số ~n (1 \leq n \leq 1000)~ và số ~m (0 \leq m \leq 10000)~. ~m~ dòng tiếp theo là 2 số ~u, v~ tức là có đường một chiều nối địa điểm ~u~ với địa điểm ~v~.

Output

Với mỗi test ghi ra trên một dòng “Case “ + case number + “: “ + kết quả.

Example

3 
5 4 
1 2
1 3
4 1
5 1
7 0
8 8
1 2
2 3
3 4
4 1
1 6
6 7
7 8
8 6

Case 1: 2
Case 2: 7
Case 3: 2