title: Optimizing python code
body: <p>Any tips on optimizing this python code for <strong>finding next palindrome</strong>:</p>
  
  <p>Input number can be of 1000000 digits</p>
  
  <p><strong>COMMENTS ADDED</strong></p>
  
  <pre><code>#! /usr/bin/python
      def inc(lst,lng):#this function first extract the left half of the string then
                       #convert it to int then increment it then reconvert it to string
                       #then reverse  it and finally append it to the left half. 
                       #lst is input number and lng is its length
          if(lng%2==0):
  
              olst=lst[:lng/2]
              l=int(lng/2)
              olst=int(olst)
              olst+=1
              olst=str(olst)
              p=len(olst)
              if l&lt;p:
                  olst2=olst[p-2::-1]
              else:
                  olst2=olst[::-1]
              lst=olst+olst2
              return lst
          else:
              olst=lst[:lng/2+1]
              l=int(lng/2+1)
              olst=int(olst)
              olst+=1
              olst=str(olst)
              p=len(olst)
              if l&lt;p:
                  olst2=olst[p-3::-1]
              else:
                  olst2=olst[p-2::-1]
              lst=olst+olst2
              return lst
  
  
  
      t=raw_input()
      t=int(t)
  
      while True:
          if t&gt;0:
              t-=1
          else:
              break
  
          num=raw_input()#this is input number
          lng=len(num)
          lst=num[:]
  
          if(lng%2==0):#this if find next palindrome to num variable
                       #without incrementing the middle digit and store it in lst.
  
              olst=lst[:lng/2]
              olst2=olst[::-1]
              lst=olst+olst2
  
          else:
              olst=lst[:lng/2+1]
              olst2=olst[len(olst)-2::-1]
              lst=olst+olst2
  
          if int(num)&gt;=int(lst):#chk if lst satisfies criteria for next palindrome
              num=inc(num,lng)#otherwise call inc function
              print num
          else:
              print lst
  </code></pre>