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

문제

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+OSwgZGlnaXQpLCBcdWMyMThcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4KG51bWJlcilcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0Jm5ic3A7XHVjMjE4XHVjNzc4IFx1YzgxNVx1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48YnIgXC8+XHJcblx1YjJlNFx1Yzc0YyBUXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc0MCBcdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MWMgXHViNDUwIFx1YzIxOCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyBUICZsZTsgNzc3Nyw8XC9saT5cclxuXHQ8bGk+MSAmbGU7IEEgJmxlOyBCICZsZTsgMTAwMDAwMDAwMDAwMCAoMTA8c3VwPjEyPFwvc3VwPik8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc0MCBcdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NWMgQSBcdWM3NzRcdWMwYzEgQiBcdWM3NzRcdWQ1NThcdWM3NTggPHN0cm9uZz5cdWM1YzRcdWNjYWRcdWIwOWMmbmJzcDtcdWQ1ODlcdWM2YjRcdWM3NTggXHVjMjE4PFwvc3Ryb25nPlx1YjRlNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgVFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWI5YzhcdWM5YzBcdWI5YzkgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NWMgPHN0cm9uZz5cdWM1YzRcdWNjYWRcdWIwOWMmbmJzcDtcdWQ1ODlcdWM2YjRcdWM3NTggXHVjMjE4PFwvc3Ryb25nPlx1YjI5NCA0LCA3LCAxNig0KjQpLCAyOCg0KjcpLCA0NCwgNDcsIDQ5KDcqNyksIDY0KDQqNCo0KSwgNzQsIDc3XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzc1MSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikx1Y2t5IG51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPkpvaG4gaGFzIHJlY2VudGx5IGFycml2ZWQgaW4gQnVjaGFyZXN0IGZvciB0aGUgU291dGggRWFzdGVybiBFdXJvcGVhbiBSZWdpb25hbCBDb250ZXN0LiBKb2huIGlzIGZhbW91cyBmb3IgaGlzIHRoZW9yeSBvZiBsdWNreSBudW1iZXJzLiBUaGF0JnJzcXVvO3Mgd2h5IGFsbCB0aGUgY29udGVzdGFudHMgYW5kIHNwZWN0YXRvcnMgYXJlIHZlcnkgaGFwcHkuIEFjY29yZGluZyB0byB0aGF0IHRoZW9yeSA0IGFuZCA3IGFyZSBsdWNreSBkaWdpdHMsIGFuZCBhbGwgdGhlIG90aGVyIGRpZ2l0cyBhcmUgbm90IGx1Y2t5LiBBIGx1Y2t5IG51bWJlciBpcyBhIG51bWJlciB0aGF0IGNvbnRhaW5zIG9ubHkgbHVja3kgZGlnaXRzIGluIGRlY2ltYWwgbm90YXRpb24uIEEgdmVyeSBsdWNreSBudW1iZXIgaXMgYSBudW1iZXIgdGhhdCBjYW4gYmUgZXhwcmVzc2VkIGFzIGEgcHJvZHVjdCBvZiBzZXZlcmFsIGx1Y2t5IG51bWJlcnMuIEEgbHVja3kgbnVtYmVyIGJ5IGl0c2VsZiBpcyBjb25zaWRlcmVkIHRvIGJlIHZlcnkgbHVja3kuIEZvciBleGFtcGxlLCBudW1iZXJzIDQ3LCA0OSwgMTEyIGFyZSB2ZXJ5IGx1Y2t5LjxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gY2FsY3VsYXRlIHRoZSBudW1iZXIgb2YgdmVyeSBsdWNreSBudW1iZXJzIHRoYXQgYXJlIG5vdCBsZXNzIHRoYW4gQSBhbmQgbm90IGdyZWF0ZXIgdGhhbiBCLiBPZiBjb3Vyc2UsIG51bWJlcnMgQSBhbmQgQiBhcmUgZ2l2ZW4gYnkgSm9obi4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIFQgJm5kYXNoOyBhIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBFYWNoIG9mIHRoZSBuZXh0IFQgbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSAmbmRhc2g7IEEgYW5kIEIuPFwvcD5cclxuXHJcbjxwPkNvbnN0cmFpbnM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSAmbGU7IFQgJmxlOyA3Nzc3LDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgQSAmbGU7IEIgJmxlOyAxMDAwMDAwMDAwMDAwICgxMDxzdXA+MTI8XC9zdXA+KS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBtdXN0IGNvbnRhaW4gVCBsaW5lcyAmbmRhc2g7IGFuc3dlcnMgZm9yIHRoZSB0ZXN0IGNhc2VzLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5WZXJ5IGx1Y2t5IG51bWJlcnMgZm9yIHRoZSBsIGFzIDQsIDcsIDE2LCAyOCwgNDQsIDQ3LCA0OSwgNjQsIDc0IGFuZCA3Ny48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==