背景

本站蓝桥杯 2026 省赛测试数据均为洛谷自造，与官方数据可能存在差异，仅供学习参考。

题目描述

给定三个整数 $N, X, Y$。请计算有多少个长度为 $N$ 的整数数组 $A$ 满足以下条件：

1. 数组 $A$ 中的每个元素 $A_i$ 都满足 $X \le A_i \le Y$；
2. 对于数组 $A$ 中的任意一个连续子数组，对其进行一次循环右移操作，得到的新子数组与原数组完全一致。

循环右移：对一个长度为 $k$ 的连续子数组 $[B_1, B_2, \dots, B_k]$ 执行一次循环右移操作，是指将该子数组变换为 $[B_k, B_1, B_2, ..., B_{k-1}]$（即把最后一个元素移到最开头，其余元素保持原有顺序依次向后顺延一位）。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

接下来的 $T$ 行，每行包含三个由空格隔开的整数 $N, X, Y$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示满足条件的数组 $A$ 的个数。

3
3 1 2
5 10 10
2 5 3

2
1
0

提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le T \le 20$, $1 \le N \le 100$, $1 \le X, Y \le 100$;

对于 $100\%$ 的评测用例，$1 \le T \le 10^3$, $1 \le N \le 10^{18}$, $1 \le X, Y \le 10^{18}$。