The winter is coming soon, and we have to keep people warm from harsh winter nights. There are M people in the town lying on a straight line at position 0, 1, 2, ..., M − 1. There are n sheets of blankets. Each sheet is infinitely long, but only some portions of it are thick enough to prevent you from freezing. Each blanket can be described by two integers (a, b). The blanket starts with a thick portion of length a, then a thin portion of length b − a, and this alternating pattern continues indefinitely. For example, if the blanket is given as (2, 3), then the first thick portion will cover persons at positions 0, 1, and the second thick portion will cover persons at positions 3, 4, and so on. We lay all blankets altogether, all start at position 0. Depends on the pattern of each blanket, some lucky people will be covered by several thick portions from different blankets while unlucky one won’t be covered at all. Your task is to count the number of people that are covered by exactly 0, 1, 2, ..., n thick blankets, respectively. Input The first line of input contains one integer T, the number of test cases (1 ≤ T ≤ 10). This is followed by T test cases, each uses the following format. • The first line contains two integers n and M (1 ≤ n ≤ 105, 1 ≤ M ≤ 106) — the number of blankets and the number of people in town. • Each of the next n lines contains two integers a and b, (1 ≤ a ≤ b ≤ 16), describing each blanket. Output For each test case, the output must contains n+1 integers, one per line, which are the number of people covered by 0, 1, 2, ..., n thick blankets, respectively. Sample Input 1 3 30 25 35 36 Sample Output 6 9 9 6