You have an array of size N initially filled with 0. You have Q queries. In each query, you will be given two integers a and b. For each query, you need to add 1 at the following valid indices: ... ... , a - 2*b, a - b, a, a + b, a + 2 * b ... ... The indices that lie in the range [1, N] are only considered valid. Print the final array after the last update. 

Input

The first line contains the number of test cases. Then T test cases follow. Every test case starts with two integers N and Q. After that, Q lines follow. In each line there will be two integers describing that query. 

1 <= T <= 10

1 <= N, Q, a, b <= 100000

Output

Print the final array after the last query with the case number. 

Example

Input:
1
5 1
1 2

Output:
Case 1: 1 0 1 0 1