描述

已知整数 ​a​,​b​,​c​,​d​，求满足以下条件的整数对 (​x​,​y​) 的数量：

a <= x <= b, c <= y <= d, x * y 是 2026 的倍数

格式

Input

• 先输入 ​T​, 表示包含 T （1<=T <= 1e6）组测试用例。
• 接着输入T 行，每行包含四个整数，分别为 ​a,b,c,d (1<= a,b,c,d <= 1e6 )

Output

对于每组测试用例，输出一个整数，该整数表示对应测试用例的求解结果（即满足a≤​x≤​b，c≤y≤d 且 x∗y是2026倍数的整数对 (​x​,​y​) 的数量）

样例

3
1 2 1 2026
1 2026 1 2026
1 100000 1 100000

3
6075
14692797

限制

1s, 1024KiB for each test case.