On Penacony, The Land of the Dreams, there exists n houses and n roads. There exists a road between house i and i+1 for all 1 <= q i <= q n-1 and a road between house n and house 1 . All roads are bidirectional. However, due to the crisis on Penacony, the overseeing family has gone into debt and may not be able to maintain all roads. There are m pairs of friendships between the residents of Penacony. If the resident living in house a is friends with the resident living in house b , there must be a path between houses a and b through maintained roads. What is the minimum number of roads that must be maintained? The first line contains t ( 1 <= q t <= q 10^4 ) – the number of test cases. The first line of each test case contains two integers n and m ( 3 <= q n <= q 2 cdot 10^5, 1 <= q m <= q 2 cdot 10^5 ) – the number of houses and the number of friendships. The next m lines contain two integers a and b ( 1 <= q a < b <= q n ) – the resident in house a is friends with the resident in house b . It is guaranteed all ( a, b ) are distinct. It is guaranteed the sum of n and m over all test cases does not exceed 2 cdot 10^5 . For each test case, output an integer, the minimum number of roads that must be maintained. For the first test case, the following roads must be maintained: