Background

放假啦放假啦，但作为ACM的一员，并没有完全放假。三次走位躲掉出题后，小L还是迎来了出题的一周。愁眉苦脸的小L看了侄子的一道数学题：给出一串数，求出所有数的最大公约数，小L表示对于小学生可能很简单，但对于他这个大学生来说还是太困难了。他灵机一动，准备拿这个来考考聪明的你，但你作为ACM界的“小学生”，他要给你上压力了。

Description

有一串全为1的数，经过m次操作后，求该数列的最大公约数。 操作为： 对于下标为l到r的数乘上x（2<=x<=3）.

Input

该题有多组输入，第一行输入一个整数T，表示你将要进行测试用例的个数

第二行输入两个整数n(1<=n<=1e5)和m(1<=M<=1e3)，分别表示数列的长度以及进行操作的次数

接下来的m行，每行输入l，r，x(记得开longlong)三个数据，分别表示操作的始末位置，以及操作数（x是整数)

Output

对于每个测试用例，都会有一个相应的数据输出表示数列的最大公约数，由于数据可能很大需要最后结果对999999998进行取模

3
10 3
3 5 3
2 6 2
3 4 3
5 3
1 5 3
2 3 2
4 5 3
5 3
1 5 2
3 4 3
3 4 2

1
3
2

1
5 4
1 5 3
1 5 3
2 3 2
4 5 2

9

Limitation

1s, 1024KiB for each test case.