Migrated from Lutece 1138 邱老师选妹子(二)

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

邱老师长得帅这是人尽皆知，于是追他的妹子就会很多。但是你知道，邱老师是一个很专一的人，所以他心里面只能有一个人。于是他决定从追他的众多妹子里挑选一个出来。

在第一轮的选拔中，剩余了一些妹子。酱神又给邱老师出主意了，因为最近酱神刚刚学习了最长上升子序列，所以这次，依然是把妹子们编号，从l到r，一共r-l+1个，这次要求妹子的

编号按照字符来处理，使得最长上升子序列正好是k，比如123是3，321是1.

求剩下的妹子的个数

Input

一开始是一个整数t<=1000，表示的是数据组数，接下来t行，每行是l，r，k 0<l<=r<2^63-1 1<=k<=10

Output

每组数据输出占一行，为一个整数，表示剩下的妹子的个数

Samples

1
123 321 2

139

Resources

2015 UESTC Training for Dynamic Programming