题号：NC23998
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
CSL 最近对勾股定理很感兴趣，他很想知道 
在 n 以内满足 
的正整数解的个数。
机智的 OneDay 很轻松的解决了他的问题。
当然 CSL 还是没那么好应付的，他想了想，给出了 OneDay 一个新的难题，他说：我现在一口气问你 q 次，你还能回答上来吗？
这可难倒了 OneDay，他来向你求助了。
定义 S(n) 为 在 n 以内满足 的正整数解的个数；%3D%5Csum%5Climits_%7Bi%3D0%7D%5E%7Bn%7D%20%5Clfloor%20%5Cfrac%7B4i%2B3%7D%7B5%7D%20%5Crfloor)
。
现在给出一个 n ，然后给出 q 次询问，每次询问给出一组 l 和 r ，计算))
由于答案可能很大，所以请将结果对 998244353 取模。
机智的 OneDay 很轻松的解决了他的问题。
当然 CSL 还是没那么好应付的，他想了想，给出了 OneDay 一个新的难题，他说：我现在一口气问你 q 次，你还能回答上来吗？
这可难倒了 OneDay，他来向你求助了。
定义 S(n) 为
现在给出一个 n ，然后给出 q 次询问，每次询问给出一组 l 和 r ，计算
由于答案可能很大，所以请将结果对 998244353 取模。
输入描述:
第一行有两个整数 n 和 q ，含义如题目描述中所述。接下来 q 行，每行两个整数 l 和 r，表示一次询问。
输出描述:
对于每一次询问，在一行输出一个整数表示该次询问答案。