It is said that Columbus once invented card games. After thousands of years, all kinds of card games have spread all over the world. Shuffling the deck is an inevitable task, because no one wants to play the same game twice. There are usually 54 cards in a deck, and we usually shuffle the deck by repeatedly taking out a sequence of cards and put them onto the top of the deck. The following figure illustrates the effect of a single shuffle.
A single shuffle with P = 2 and L = 3 will move the white cards onto the top
To help people shuffle, Edison invented a machine, namely Automated Card-shuffling Machine. The machine is controlled by instructions, which give the starting position P and the length L of the sequence. Of course the instructions are generated by a randomizer. Unfortunately it is discovered that the randomizer has a bug that leads to repetitive instructions. That is, several consecutive instructions may be exactly the same. Though despaired, Edison decides to pack the repetitive instructions into a single "extended instruction" and ship this machine off to the market. An extended instruction consists of not only P and L for a sequence, but also the number of times R it repeats.
Input Description
Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.
The first line of each test case contains two integers C (0 < C <= 1,000,000) and S (0 <= S <= 5,000). The deck holds C cards, numbered from 0 to C - 1, and we will do S shuffles.
The following S lines contain three integers each, Pi (0 <= Pi < C), Li (1 <= Li <= C) and Ri (1 <= Ri <= 100), 1 <= i <= S. Each line represents an extended instruction. Note that the card on the top has a position of 0. It is guaranteed that Pi + Li <= C.
Output Description
Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.
For each test case, print the sum of the card numbers at odd positions of deck after shuffling.
Sample Input
2
10 1
5 3 1
10 3
5 3 1
2 4 1
7 2 2
Sample Output
Case 1:
24
Case 2:
23
HINT: The cards on the decks after shuffling would be:
Case 1 �C 5 6 7 0 1 2 3 4 8 9 (5 + 7 + 1 + 3 + 8 = 24)
Case 2 �C 6 3 4 8 7 0 1 2 5 9 (6 + 4 + 7 + 1 + 5 = 23)
