火星之上的住民是使用4进制的,因为他们的手指很少。火星上面的单身小伙小姑娘们都很讨厌5这个数,因为这个数在4进制下的表示是”11”。
给定一个区间[L,R],计算这个区间内有多少数x,使得x在4进制下的表示不包含任何5的正倍数,0不计算在内,比如4进制下101这个数不包含”11”的倍数。
Hint:就是一个数x,转换成4进制之后,其子串中不包含11,22,33,110,121,132……,因为这些是4进制下11的倍数,比如4进制下112由于包含11因此这个数不算,但是10,100,1000是允许的,1001不允许是因为1001本身是4进制下11的倍数。
多组数据,每组数据2个正整数L,R保证1<=L<=R<=10^9(L,R都以10进制给出)
输出区间内这样的数的个数。
1 10
1 20
8
16
第二组样例中,11,22,33,110包含了11的倍数