小鱼的航程hard

与easy版本不同的地方有：T组数据以及N的范围 本题要用周期来优化

题目背景

题目描述

有一只小鱼，它平日每天游泳 $250$ 公里，周末休息（实行双休日)，假设从周 $x$ 开始算起，过了 $n$ 天以后，小鱼一共累计游泳了多少公里呢？

输入格式

第一行输入一个T，表示有T组数据要处理 $(1 \leq T \leq 10000)$

每一组数据输入两个正整数 $x,n$，表示从周 $x$ 算起，经过 $n$ 天。

数据保证，$1\le x \le 7$，$1 \le n\le 10^{14}$。

输出格式

输出一个整数，表示小鱼累计游泳了多少公里。

样例 #1

样例输入 #1

2
2 1000000000
4 123123123

样例输出 #1

178571428500
21986271750