A network has n routers, uniquely numbered from 1 to n. Two routers can communicate with each other, if either they are directly connected, or one of them is connected with someone, that can communicate with the other (indirectly connected). Now, connect these n routers in such a way that after any m routers become inactive all other active routers can communicate among each other directly or through a series of active routers. But the number of connections should not exceed ceil (((m + 1) ∗ n)/2). All the communication links are bidirectional. Input First line of the input contains T the number of test cases. Each test case contains 2 integers in one line n (1 ≤ n ≤ 50) and m (1 ≤ m ≤ 10 and m < (n − 2)). Output For each test case output should contain e + 2 lines where e is the number of connections needed. First line contains e. line 2 to e + 1 contains 2 integers i and j denoting that there should be a connection between the router i and router j. line e + 2 is blank. Sample Input 1 41 Sample Output 4 12 23 34 41