시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1 1 1 100.000%

문제

John은 최근에 지역 대회를 위해 동부 유럽의 부쿠레슈티에 도착하였다. John은 그의 행운의 수 이론으로 유명하다. 대회 참여자와 관전자가 매우 행복해하는 이유가 그것이다. 그의 행운의 수 이론에 따르면, 4와 7은 행운의 숫자(0~9)고, 이외의 숫자(0~9)는 그렇지 않은 숫자이다. 행운의 수는 10진수 표현 방식에서 행운의 숫자로만 이루어져 있는 수이다. 엄청난 행운의 수는 몇몇 행운의 수의 곱으로 나타낼 수 있는 수이다. 행운의 수 그 자체는 엄청난 행운의 수로도 본다.  예를 들어, 47(47), 49(7*7), 112(4*7*7)은 엄청난 행운의 수이다.

당신이 해야 할 일은 A 이상 B 이하의 엄청난 행운의 수들의 개수를 계산하는 것이다.  물론, A와 B는 John이 준다.

  • 숫자는 1자리 수(0~9, digit), 수는 자연수(number)를 의미한다.

입력

첫번째 줄에 테스트 케이스 수인 정수 T가 주어진다.
다음 T개의 줄은 각 줄마다 공백으로 구분된 두 수 A와 B가 주어진다.

  • 1 ≤ T ≤ 7777,
  • 1 ≤ A ≤ B ≤ 1000000000000 (1012)

출력

출력은 각각의 테스트 케이스에 대한 A 이상 B 이하의 엄청난 행운의 수들의 개수를 T개의 줄로 출력한다.

예제 입력 1

4
1 2
88 99
112 112
1 100

예제 출력 1

0
0
1
10

힌트

마지막 테스트 케이스에 대한 엄청난 행운의 수는 4, 7, 16(4*4), 28(4*7), 44, 47, 49(7*7), 64(4*4*4), 74, 77이다.

W3sicHJvYmxlbV9pZCI6IjM3NTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1ODlcdWM2YjRcdWM3NTggXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5Kb2huXHVjNzQwIFx1Y2Q1Y1x1YWRmY1x1YzVkMCBcdWM5YzBcdWM1ZWQgXHViMzAwXHVkNjhjXHViOTdjIFx1YzcwNFx1ZDU3NCBcdWIzZDlcdWJkODAgXHVjNzIwXHViN2ZkXHVjNzU4IFx1YmQ4MFx1Y2ZlMFx1YjgwOFx1YzI4OFx1ZDJmMFx1YzVkMCBcdWIzYzRcdWNjMjlcdWQ1NThcdWM2MDBcdWIyZTQuIEpvaG5cdWM3NDAgXHVhZGY4XHVjNzU4IFx1ZDU4OVx1YzZiNFx1Yzc1OCBcdWMyMTggXHVjNzc0XHViODYwXHVjNzNjXHViODVjIFx1YzcyMFx1YmE4NVx1ZDU1OFx1YjJlNC4mbmJzcDtcdWIzMDBcdWQ2OGMgXHVjYzM4XHVjNWVjXHVjNzkwXHVjNjQwIFx1YWQwMFx1YzgwNFx1Yzc5MFx1YWMwMCBcdWI5ZTRcdWM2YjAgXHVkNTg5XHViY2Y1XHVkNTc0XHVkNTU4XHViMjk0IFx1Yzc3NFx1YzcyMFx1YWMwMCBcdWFkZjhcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWRmOFx1Yzc1OCBcdWQ1ODlcdWM2YjRcdWM3NTggXHVjMjE4IFx1Yzc3NFx1Yjg2MFx1YzVkMCBcdWI1MzBcdWI5NzRcdWJhNzQsIDRcdWM2NDAgN1x1Yzc0MCBcdWQ1ODlcdWM2YjRcdWM3NTggXHVjMjJiXHVjNzkwKDB+OSlcdWFjZTAsIFx1Yzc3NFx1YzY3OFx1Yzc1OCBcdWMyMmJcdWM3OTAoMH45KVx1YjI5NCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YzIyYlx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHVkNTg5XHVjNmI0XHVjNzU4IFx1YzIxOFx1YjI5NCAxMFx1YzljNFx1YzIxOCBcdWQ0NWNcdWQ2MDQgXHViYzI5XHVjMmRkXHVjNWQwXHVjMTFjIFx1ZDU4OVx1YzZiNFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NzRcdWIyZTQuIDxzdHJvbmc+XHVjNWM0XHVjY2FkXHViMDljIFx1ZDU4OVx1YzZiNFx1Yzc1OCBcdWMyMTg8XC9zdHJvbmc+XHViMjk0IFx1YmE4N1x1YmE4NyBcdWQ1ODlcdWM2YjRcdWM3NTggXHVjMjE4XHVjNzU4IFx1YWNmMVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMyMThcdWM3NzRcdWIyZTQuIDx1Plx1ZDU4OVx1YzZiNFx1Yzc1OCBcdWMyMTgmbmJzcDtcdWFkZjggXHVjNzkwXHVjY2I0XHViMjk0IDxzdHJvbmc+XHVjNWM0XHVjY2FkXHViMDljIFx1ZDU4OVx1YzZiNFx1Yzc1OCBcdWMyMTg8XC9zdHJvbmc+XHViODVjXHViM2M0IFx1YmNmOFx1YjJlNC48XC91PiAmbmJzcDtcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCA0Nyg0NyksIDQ5KDcqNyksIDExMig0KjcqNylcdWM3NDAgXHVjNWM0XHVjY2FkXHViMDljJm5ic3A7XHVkNTg5XHVjNmI0XHVjNzU4IFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzc0IFx1ZDU3NFx1YzU3YyBcdWQ1NjAgXHVjNzdjXHVjNzQwIEEgXHVjNzc0XHVjMGMxIEIgXHVjNzc0XHVkNTU4XHVjNzU4Jm5ic3A7PHN0cm9uZz5cdWM1YzRcdWNjYWRcdWIwOWMmbmJzcDtcdWQ1ODlcdWM2YjRcdWM3NTggXHVjMjE4PFwvc3Ryb25nPlx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gJm5ic3A7XHViYjNjXHViODYwLCBBXHVjNjQwIEJcdWIyOTQgSm9oblx1Yzc3NCBcdWM5MDBcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjMjJiXHVjNzkwXHViMjk0IDFcdWM3OTBcdWI5YWMgXHVjMjE4KDB+OSwgZGlnaXQpLCBcdWMyMThcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4KG51bWJlcilcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQmbmJzcDtcdWMyMThcdWM3NzggXHVjODE1XHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxiciBcLz5cclxuXHViMmU0XHVjNzRjIFRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzQwIFx1YWMwMSBcdWM5MDRcdWI5YzhcdWIyZTQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyBcdWI0NTAgXHVjMjE4IEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IFQgJmxlOyA3Nzc3LDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgQSAmbGU7IEIgJmxlOyAxMDAwMDAwMDAwMDAwICgxMDxzdXA+MTI8XC9zdXA+KTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU1YyBBIFx1Yzc3NFx1YzBjMSBCIFx1Yzc3NFx1ZDU1OFx1Yzc1OCA8c3Ryb25nPlx1YzVjNFx1Y2NhZFx1YjA5YyZuYnNwO1x1ZDU4OVx1YzZiNFx1Yzc1OCBcdWMyMTg8XC9zdHJvbmc+XHViNGU0XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBUXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU1YyA8c3Ryb25nPlx1YzVjNFx1Y2NhZFx1YjA5YyZuYnNwO1x1ZDU4OVx1YzZiNFx1Yzc1OCBcdWMyMTg8XC9zdHJvbmc+XHViMjk0IDQsIDcsIDE2KDQqNCksIDI4KDQqNyksIDQ0LCA0NywgNDkoNyo3KSwgNjQoNCo0KjQpLCA3NCwgNzdcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNzUxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTHVja3kgbnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+Sm9obiBoYXMgcmVjZW50bHkgYXJyaXZlZCBpbiBCdWNoYXJlc3QgZm9yIHRoZSBTb3V0aCBFYXN0ZXJuIEV1cm9wZWFuIFJlZ2lvbmFsIENvbnRlc3QuIEpvaG4gaXMgZmFtb3VzIGZvciBoaXMgdGhlb3J5IG9mIGx1Y2t5IG51bWJlcnMuIFRoYXQmcnNxdW87cyB3aHkgYWxsIHRoZSBjb250ZXN0YW50cyBhbmQgc3BlY3RhdG9ycyBhcmUgdmVyeSBoYXBweS4gQWNjb3JkaW5nIHRvIHRoYXQgdGhlb3J5IDQgYW5kIDcgYXJlIGx1Y2t5IGRpZ2l0cywgYW5kIGFsbCB0aGUgb3RoZXIgZGlnaXRzIGFyZSBub3QgbHVja3kuIEEgbHVja3kgbnVtYmVyIGlzIGEgbnVtYmVyIHRoYXQgY29udGFpbnMgb25seSBsdWNreSBkaWdpdHMgaW4gZGVjaW1hbCBub3RhdGlvbi4gQSB2ZXJ5IGx1Y2t5IG51bWJlciBpcyBhIG51bWJlciB0aGF0IGNhbiBiZSBleHByZXNzZWQgYXMgYSBwcm9kdWN0IG9mIHNldmVyYWwgbHVja3kgbnVtYmVycy4gQSBsdWNreSBudW1iZXIgYnkgaXRzZWxmIGlzIGNvbnNpZGVyZWQgdG8gYmUgdmVyeSBsdWNreS4gRm9yIGV4YW1wbGUsIG51bWJlcnMgNDcsIDQ5LCAxMTIgYXJlIHZlcnkgbHVja3kuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiB2ZXJ5IGx1Y2t5IG51bWJlcnMgdGhhdCBhcmUgbm90IGxlc3MgdGhhbiBBIGFuZCBub3QgZ3JlYXRlciB0aGFuIEIuIE9mIGNvdXJzZSwgbnVtYmVycyBBIGFuZCBCIGFyZSBnaXZlbiBieSBKb2huLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgVCAmbmRhc2g7IGEgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEVhY2ggb2YgdGhlIG5leHQgVCBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlICZuZGFzaDsgQSBhbmQgQi48XC9wPlxyXG5cclxuPHA+Q29uc3RyYWluczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgVCAmbGU7IDc3NzcsPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBBICZsZTsgQiAmbGU7IDEwMDAwMDAwMDAwMDAgKDEwPHN1cD4xMjxcL3N1cD4pLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG11c3QgY29udGFpbiBUIGxpbmVzICZuZGFzaDsgYW5zd2VycyBmb3IgdGhlIHRlc3QgY2FzZXMuPFwvcD5cclxuIiwiaGludCI6IjxwPlZlcnkgbHVja3kgbnVtYmVycyBmb3IgdGhlIGwgYXMgNCwgNywgMTYsIDI4LCA0NCwgNDcsIDQ5LCA2NCwgNzQgYW5kIDc3LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d