小 A 最近开始制定健身计划。他计划连续锻炼 n 天，每天选择一项训练项目。

为了保证运动强度的多样性，他为第 i 天设置了一个训练强度 x_i，这个训练强度 x_i 在 [a_i, b_i] 的范围内，当天的体力消耗为 x_i^2。

请你编程帮助小 A 计算出，他 n 天的锻炼一共的体力消耗，有多少种不同的可能取值？

形式化的说，如果用 S 表示他 n 天的体力消耗，那么有 S = x_1^2 + x_2^2 + \cdots + x_n^2，你需要编程计算出 S 的值有多少种不同的可能？

第一行包含一个整数 n，表示训练天数。

接下来的 n 行，每行两个整数 a_i 和 b_i，表示第 i 天训练强度的选择范围是 [a_i, b_i]。

输出一行一个整数，表示 S 可能的种类数。

数据范围

对于所有的测评数据，满足 1 \leq n \leq 100，1 \leq a_i \leq b_i \leq 100。

bitset动态规划