Server Time: Tue Oct 23, 2018 9:18 pm
Welcome ( logout
1135 - Count the Multiples of 3
  PDF (English) Statistics Forum
Time Limit: 3 second(s) Memory Limit: 64 MB

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

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 Input

Output for Sample Input

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

Note

Dataset is huge, use faster i/o methods.


Special Thanks: Jane Alam Jan (Description, Solution, Dataset)
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan