Василько придумав інтелектуальну гру. Він розглядає квадратну таблицю розмірності \(N\). Всі клітинки \((x,y)\), які задовольняють умову \(x*y≤N\) він зафарбував. Тепер він рахує всі можливі прямокутники, що містять зафарбовані клітинки і не містять не фарбованих.
Наприклад, при \(N=4\) зафарбованими будуть такі клітинки: (1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (3,1), (4,1).
Василько хоче точно знати скільки є всього можливих варіантів прямокутників, які містять лише зафарбовані клітинки. Допоможіть йому.
Оскільки це число може бути досить великим, то треба вивести його по модулю 1000000007.
Формат вхідних даних
Перший рядок вхідного потоку містить ціле число \(Т\) \((1 ≤ T ≤ 5)\) — кількість тестів.
Єдиний рядок кожного тесту містить ціле \(N\) \((1 ≤ N ≤ 10^{10})\).
Формат вихідних даних
Для кодного тесту вивести шукану кількість прямокутників по модулю 1000000007.
Приклад вхідних даних
2
4
10000000000
Приклад вихідних даних
23
227374950
Коментарі