Description

东北的天气从11月就开始变冷了，懒惰的小明觉得躺在床上比冒着寒风去8号楼敲代码舒服多了，美其名曰：我要在宿舍敲代码！！！（gui知道他干了啥）。

于是他做出如下决定 ：

• 每周只会选择在周一、周三、周五、周日这4 天去8号楼；

• 如果这天下了大雨或者大雪的话，也不去（即如果某一天下了大雨或大雪，无论这一天是周几，懒惰的小明都不会去8号楼）。

突发奇想，学长们想统计一下在11月（假设该月1号是星期一）的某个时间段小明来8号楼签到的次数（小明每次来都会签到）。

Format

Input

首行输入正整数t ( 1 ≤ t ≤ 100) 。

接着有t 行：

每行有三个数l, r, k(表示在从l 号到r 号的这个时间段，有k 天下了大雨或者大雪，1 ≤ l ≤ r ≤ 30，k ≤ r - l + 1 ）。

Output

对于每次时间段的查询，输出在该时间段小明可能签到的最少 次数。

Samples

2
1 7 1
2 3 1

3
0

Hint