题目描述

青禾与砚秋分别在两处遗迹中找到了引火纹和回响纹。只有选出能够产生共鸣的一对灵纹刻度，沉睡的灯芯才会现身。

一次共鸣试验需要选定一对有序的灵纹刻度 $(x,y)$。引火纹刻度 $x$ 必须位于区间 $[l_1,r_1]$ 内，回响纹刻度 $y$ 必须位于区间 $[l_2,r_2]$ 内。

古籍记载，灵纹的共鸣倍率以整数 $k$ 为基础。只有当存在一个非负整数 $n$，使得

这对灵纹刻度才能产生共鸣。

请你计算，共有多少对有序数对 $(x,y)$ 能够产生共鸣。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量。

接下来 $t$ 行，每行包含五个整数 $k,l_1,r_1,l_2,r_2$，表示一组测试用例。

输出格式

对于每个测试用例，输出一行一个整数，表示满足条件的有序数对 $(x,y)$ 的数量。

输入输出样例

输入 #1

5
2 2 6 2 12
2 1 1000000000 1 1000000000
3 5 7 15 63
1000000000 1 5 6 1000000000
15 17 78 2596 20914861

输出 #1

12
1999999987
6
1
197

说明与限制

• $1\le t\le 10^4$
• $2\le k\le 10^9$
• $1\le l_1\le r_1\le 10^9$
• $1\le l_2\le r_2\le 10^9$

对于第三个测试用例，能够产生共鸣的有序数对为：

对于第四个测试用例，唯一能够产生共鸣的有序数对是 $(1,1000000000)$。