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:

1. Increase the numbers between indices i and j (inclusive) by 1. This is represented by the command '0 i j'.
2. Answer how many numbers between indices i and j (inclusive) are divisible by 3. This is represented by the command '1 i j'.

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 ≤ 10⁵) 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.

For each case, print the case number first. Then for each query in the form '1 i j', print the desired result.

Dataset is huge, use faster I/O methods.