Read problems statements in Mandarin Chinese and Russian as well. 

Euler's phi function  for a positive integer N is usually denoted as φ(N) and defined as the number of positive integers less than or equal to N that are  coprime with N. Let's call a positive integer N a super number if N can be divided by φ(N) without a remainder.  
e.g. 2 is a super number (since 2 mod φ(2) = 0), while 3 is not (since 3 mod φ(3) = 1).

You are given two positive integers L and R. Your task is to find count of super numbers in the range [L, R].

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

Each test case is described by a single line containing two positive integers L and R.

------ Output ------ 

For each test case, output a single line containing one integer: the number of super numbers in the range.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ L ≤ R ≤ 10^{18}$

----- Sample Input 1 ------ 
3
2 3
90 95
12 21
----- Sample Output 1 ------ 
1
0
3
----- explanation 1 ------ 
In the first example, 2 is a super number while 3 is not (as explained in the statement). So, the number of super numbers in the range [2, 3] will be equal to 1.

Source: codechef | Difficulty: HARD
Tags: Number theory

Mathematics


Solutions:
l = set()
l.add(1)
i = 2
while i <= 10 ** 18:
	j = 1
	while j * i <= 1000000000000000000:
		l.add(i * j)
		j *= 3
	i *= 2
lis = list(l)
lis.sort()
for _ in range(int(input())):
	cnt = 0
	(l, r) = map(int, input().split())
	for x in lis:
		if l <= x <= r:
			cnt += 1
		if x > r:
			break
	print(cnt)


import math
t = int(input())
while t:
	s = input().split()
	x = int(s[0])
	y = int(s[1])
	l2 = int(math.log2(y))
	r2 = int(math.log(y) / math.log(3))
	ans = 0
	if x == 1:
		ans += 1
	for i in range(1, l2 + 1):
		for j in range(0, r2 + 1):
			num = 2 ** i * 3 ** j
			if num >= x and num <= y:
				ans += 1
	print(ans)
	t -= 1


t = int(input())
while t > 0:
	inp = input().split()
	a = int(inp[0])
	b = int(inp[1])
	tmp = 2
	cnt = 0
	while tmp <= b:
		tmpp = tmp
		while tmpp <= b:
			if tmpp >= a:
				cnt += 1
			tmpp *= 3
		tmp *= 2
	if a == 1:
		cnt += 1
	print(cnt)
	t -= 1


from itertools import count

def solve(left, right):
	c = 0
	for i in count(start=1):
		if 2 ** i > right:
			break
		for j in count(start=0):
			mul = 2 ** i * 3 ** j
			if mul > right:
				break
			if left <= mul <= right:
				c += 1
	if left <= 1 <= right:
		c += 1
	return c
t = int(input())
for _ in range(t):
	(left, right) = map(int, input().split())
	print(solve(left, right))


def binsear(l, start, end, val):
	while end > start:
		mid = (start + end) // 2
		if l[mid] < val:
			start = mid + 1
		else:
			end = mid
	return end
tp18 = 1000000000000000000
L = [1]
p2 = 1
for x in range(65):
	p3 = 1
	for y in range(45):
		if 2 * p2 * p3 <= tp18:
			L.append(2 * p2 * p3)
		p3 *= 3
	p2 *= 2
	L.sort()
	l = len(L)
for testcasfa in range(int(input())):
	(x, y) = [int(x) for x in input().split()]
	print(binsear(L, 0, l, y + 1) - binsear(L, 0, l, x))


R = []
T = []
MX = 10 ** 18
v = 2
while v < MX:
	T.append(v)
	v = v * 2
R = list(T)
for x in T:
	v = 3 * x
	while v < MX:
		R.append(v)
		v = 3 * v
R.append(1)
R.sort()
R.append(2 * MX)
for _ in range(int(input())):
	st = input().split()
	L = int(st[0])
	r = int(st[1])
	p = 0
	while R[p] < L:
		p += 1
	q = p
	while R[q] <= r:
		q += 1
	n = q - p
	print(n)


for _ in range(int(input())):
	(l, r) = [int(i) for i in input().split()]
	val = 2
	cnt = 0
	while val <= r:
		curr = val
		while curr <= r:
			if l <= curr <= r:
				cnt += 1
			curr *= 3
		val *= 2
	if l <= 1 <= r:
		cnt += 1
	print(cnt)


import bisect
a = []
for i in range(1, 100):
	for j in range(0, 100):
		v = 2 ** i * 3 ** j
		if v <= 1e+30:
			a.append(v)
a.sort()
a.insert(0, 1)
t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	p = bisect.bisect_left(a, l)
	n = 0
	while a[p] <= r:
		n += 1
		p += 1
	print(n)


def superNumbers(l, r):
	result = 0
	value = 2
	while value <= r:
		tmpValue = value
		while tmpValue <= r:
			if tmpValue >= l and tmpValue <= r:
				result += 1
			tmpValue *= 3
		value *= 2
	if l <= 1 and 1 <= r:
		result += 1
	return result
tc = int(input())
while tc > 0:
	(l, r) = map(int, input().split())
	result = superNumbers(l, r)
	print(result)
	tc -= 1


T = int(input())
while T > 0:
	(L, R) = map(int, input().split())
	count = 0
	if 1 >= L and 1 <= R:
		count += 1
	a = 2
	while a <= R:
		b = a
		while b <= R:
			if b >= L:
				count += 1
			b *= 3
		a *= 2
	print(count)
	T -= 1


T = int(input())
for t in range(T):
	(L, R) = map(int, input().split())
	count = 0
	if 1 >= L and 1 <= R:
		count += 1
	a = 2
	while a <= R:
		b = a
		while b <= R:
			if b >= L:
				count += 1
			b *= 3
		a *= 2
	print(count)


import bisect
a = [1]
i = 2
while i < 10 ** 18 + 1:
	a.append(i)
	j = i
	while j < 10 ** 18 + 1:
		a.append(j * 3)
		j = j * 3
	i = i * 2
a.sort()
t = int(input())
while t > 0:
	(l, r) = [int(x) for x in input().split()]
	c = 0
	i = bisect.bisect_left(a, l)
	j = bisect.bisect_left(a, r)
	if a[j] == r:
		j = j + 1
	print(j - i)
	t = t - 1


import bisect
l = set()
l.add(1)
i = 2
while i <= 10 ** 18:
	j = 1
	while j * i <= 1000000000000000000:
		l.add(i * j)
		j *= 3
	i *= 2
lis = list(l)
lis.sort()
for _ in range(int(input())):
	(left_index, rigth_index) = map(int, input().split())
	left = bisect.bisect_left(lis, left_index)
	right = bisect.bisect_right(lis, rigth_index)
	print(len(lis[left:right]))


lst = []
for i in range(1, 60):
	for j in range(40):
		if 2 ** i * 3 ** j < 10 ** 18:
			lst.append(2 ** i * 3 ** j)
lst.append(1)
x = int(input())
for i in range(x):
	(a, b) = map(int, input().split(' '))
	ct = 0
	for j in lst:
		if a <= j <= b:
			ct += 1
	print(ct)


for t in range(int(input())):
	temp = list(map(int, input().split()))
	l = temp[0]
	r = temp[1]
	val1 = 2
	ans = 0
	while val1 <= r:
		val2 = 1
		x = val1 * val2
		while x <= r:
			if x >= l and x <= r:
				ans += 1
			x *= 3
		val1 *= 2
	if 1 >= l and 1 <= r:
		ans += 1
	print(ans)


ans = [1, 2]
count = 0
for i in range(2, 100):
	if 2 ** i > 10 ** 19:
		break
	else:
		bo = 0
		so = 0
		z = 2 ** i
		for j in range(i):
			k = 2 ** i // 2 ** so
			k *= 3 ** bo
			so += 1
			bo += 1
			ans.append(k)
n = int(input())
ans.sort()
for i in range(n):
	(a, b) = map(int, input().split())
	count = 0
	for j in ans:
		if a <= j <= b:
			count += 1
		if j > b:
			break
	print(count)


T = int(input())
while T > 0:
	T -= 1
	(L, R) = map(int, input().split())
	msk2 = 2
	ans = 0
	while msk2 <= R:
		msk3 = 1
		while msk2 * msk3 <= R:
			if msk2 * msk3 >= L:
				ans += 1
			msk3 *= 3
		msk2 *= 2
	if L == 1:
		ans += 1
	print(ans)


import sys
import math
import time
import random
import functools
import fractions
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split(' '))
	cnt = 0
	if a == 1:
		cnt += 1
	for apower in range(1, 64):
		res = 2 ** apower
		while res <= b:
			if res >= a:
				cnt += 1
			res *= 3
	print(cnt)


l = set()
l.add(1)
i = 2
while i <= 10 ** 18:
	j = 1
	while j * i <= 10 ** 18:
		l.add(i * j)
		j *= 3
	i *= 2
s = list(l)
for i in range(int(input())):
	(m, r) = map(int, input().split())
	count = 0
	for i in range(len(s)):
		if s[i] >= m and s[i] <= r:
			count += 1
	print(count)


test = int(input())
while test > 0:
	test -= 1
	(L, R) = map(int, input().split())
	answer = 0
	value = 2
	while value <= R:
		current = value
		while current <= R:
			if L <= current <= R:
				answer += 1
			current *= 3
		value *= 2
	if L <= 1 <= R:
		answer += 1
	print(answer)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	(k, p) = (0, 2)
	if a <= 1 and b >= 1:
		k += 1
	while p <= b:
		q = p
		while q <= b:
			if q >= a and q <= b:
				k += 1
			q *= 3
		p *= 2
	print(k)


import heapq, bisect, math, collections, sys, fractions, copy, functools, operator, itertools, string
argmax = lambda l: l.index(max(l))
argmin = lambda l: l.index(min(l))

def read_list(t):
	return [t(x) for x in input().split()]

def read_line(t):
	return t(input())

def read_lines(t, N):
	return [t(input()) for _ in range(N)]

def main():
	array = [1]
	w = 2
	L = 10 ** 18
	while w <= L:
		u = 1
		while w * u <= L:
			array.append(w * u)
			u *= 3
		w <<= 1
	array.sort()
	for i in range(read_line(int)):
		(l, r) = read_list(int)
		(lb, ub) = (bisect.bisect_left(array, l), bisect.bisect_right(array, r))
		print(ub - lb)
main()