You have an array with n elements which is indexed from 0 to n - 1. Initially all elements are zero. Now you have to deal with two types of operations:
- Increase the numbers between indices i and j (inclusive) by 1. This is represented by the command '0 i j'.
- Answer how many numbers between indices i and j (inclusive) are divisible by 3. This is represented by the command '1 i j'.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
Each case starts with a line containing two integers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 50000) denoting the number of queries. Each query will be either in the form '0 i j' or '1 i j' where i, j are integers and 0 ≤ i ≤ j < n.
Output
For each case, print the case number first. Then for each query in the form '1 i j', print the desired result.
Sample
Sample Input | Sample Output |
---|---|
1 10 9 0 0 9 0 3 7 0 1 4 1 1 7 0 2 2 1 2 4 1 8 8 0 5 8 1 6 9 | Case 1: 2 3 0 2 |
Notes
Dataset is huge, use faster I/O methods.