單身！

依然單身！

吉哥依然單身！

DS 級(jí)碼農(nóng)吉哥依然單身！

所以，他平生最恨情人節(jié)，不管是 214 還是 77，他都討厭！

吉哥觀察了 214 和 77 這兩個(gè)數(shù)，發(fā)現(xiàn)：

2+1+4=7
7+7=7×2
77=7×11
最終，他發(fā)現(xiàn)原來(lái)這一切歸根到底都是因?yàn)楹?77 有關(guān)！所以，他現(xiàn)在甚至討厭一切和 7 有關(guān)的數(shù)！

什么樣的數(shù)和 7 有關(guān)呢？如果一個(gè)整數(shù)符合下面三個(gè)條件之一，那么我們就說(shuō)這個(gè)整數(shù)和 7 有關(guān)：

整數(shù)中某一位是 7；

整數(shù)的每一位加起來(lái)的和是 7 的整數(shù)倍；

這個(gè)整數(shù)是 7 的整數(shù)倍。

現(xiàn)在問(wèn)題來(lái)了：吉哥想知道在一定區(qū)間內(nèi)和 7 無(wú)關(guān)的數(shù)字的平方和。

輸入數(shù)據(jù)的第一行是測(cè)試數(shù)據(jù)組數(shù) T，然后接下來(lái)的 T 行表示 T 組測(cè)試數(shù)據(jù)。

每組數(shù)據(jù)在一行內(nèi)包含兩個(gè)正整數(shù) L,R。

對(duì)于每組數(shù)據(jù)，請(qǐng)計(jì)算 [L,R] 中和 7 無(wú)關(guān)的數(shù)字的平方和，并將結(jié)果對(duì) 10⁹+7 取模后輸出。

數(shù)據(jù)范圍與提示：

對(duì)于全部數(shù)據(jù)，1≤T≤50,1≤L≤R≤10¹⁸ 。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃