题目描述

在七夕的前一天,学长给我们发出了最后的通牒,暑假作业再不写你就凉了,没有女朋友的xzl没人配过七夕就出了一道签（mo）到 （ban）题 给大家开心 ，开心 ；

定义F(x) = abs(cnt1 - cnt2) ;

cnt1 = 数字x各个位数奇数的个数 ；

cnt2 = 数字x各个位数偶数的个数 ；

如 : x = 123456 ;

则123456 cnt1 = 3 ， cnt2 = 3 ；

F(x) = 0 ;

现在给出 l , r , m ， 1 <= l , r <= 1e18 , m <= 18 ;

让你求出在l 到r 中F(x) >= m 的个数 ；

输入格式

输入l , r , m , 1 <= l , r <= 1e18 , m <= 18 ;

输出格式

F(x) >= m 的个数 x ∈ [l , r] ;

样例

样例输入

1 100 0 

样例输出

100

数据范围与提示

见题面