题目描述

Bessie最近买了一台手机，它的手机号码是：13300303003，手机号码由 11 个数字组成。Bessie最近在上电脑课学了复制和粘贴，于是它打开word软件，把它的手机号码复制，然后粘贴了 N 次。

例如N = 1 时，是这样：13300303003。

又例如N = 2 时，是这样：1330030300313300303003。

再例如N = 3 时，是这样：133003030031330030300313300303003。

如果N = 4，会是这样：13300303003133003030031330030300313300303003。

现在给出了三个正整数：N，S，T。表示奶牛Bessie把它的手机号码复制粘贴了 N 次，然后奶牛要计算：第 S 个数字到第 T 个数字之间，有多少个数字 3（包含第 S 个数字和第 T 个数字）？由于奶牛Bessie复制粘贴 N 次手机号码后已经眼花了，所以它希望你能写个程序来帮它计算，你能做到吗？

输入格式

第一行，有一个整数M，表示有 M 组数据。

接下来有M 行，每行有三个整数 Ni，Si，Ti，表示奶牛Bessie把它的手机号码复制粘贴了 Ni 次后，计算第 Si 个数字到第 Ti 个数字之间数字 3 的个数。

输出格式

输出有M 行整数，第 i 行是第i组数据的结果，表示Bessie把手机号码复制粘贴 Ni 次后，第 Si 个数字到第 Ti 个数字之间包含了多少个数字 3（包含第 S 个数字和第 T 个数字）。

样例输入/输出

3
10 2 20
3 20 30
5 1 50

9
5
23

数据规模与提示

对于50% 的数据，1 ≤ N ≤ 1000，1 ≤ S ＜ T ≤ 11 × N；

对于100% 的数据，1 ≤ M ≤ 2000000 1 ≤ N ≤ 2000000，1 ≤ S ＜ T ≤ 11 × N。