You are given a bidirectional graph with N vertices and M edges. All edges are painted into either red or black. Your job is to find a spanning tree with some prime number of red edges.

Input

First line contains the number of test cases T(1≤ T ≤10).

For each test case:

First line consists of two integers denoting N(1≤ N ≤100000) and M(0≤ M ≤200000).

Next M lines consist of two integers A, B and C denoting there is a directed road from A to B (1≤ A,B ≤N) with color C(0 for black and 1 for red).The graph may contain self loops and multiple edges between two nodes.

Output

For every test case, you need to print “Case T: ” (where T is the test case number) followed by the prime number. If you can not construct such a tree print -1. If you can use multiple prime, print the largest one.